#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    unordered_map<string, vector<string>> graph;

    // city -> longest path length starting from city
    unordered_map<string, int> dp;

    // city -> next city in longest path
    unordered_map<string, string> nextCity;

    int dfs(string city) {
        if (dp.count(city))
            return dp[city];

        int maxLen = 1; // city itself

        for (auto &nbr : graph[city]) {
            int currLen = 1 + dfs(nbr);

            if (currLen > maxLen) {
                maxLen = currLen;
                nextCity[city] = nbr;
            }
        }

        return dp[city] = maxLen;
    }

public:
    vector<string> longestItinerary(
        vector<pair<string, string>>& routes) {

        unordered_set<string> allCities;

        for (auto &route : routes) {
            string from = route.first;
            string to = route.second;

            graph[from].push_back(to);

            allCities.insert(from);
            allCities.insert(to);
        }

        string startCity;
        int longestLength = 0;

        for (auto &city : allCities) {
            int len = dfs(city);

            if (len > longestLength) {
                longestLength = len;
                startCity = city;
            }
        }

        vector<string> path;

        while (!startCity.empty()) {
            path.push_back(startCity);

            if (!nextCity.count(startCity))
                break;

            startCity = nextCity[startCity];
        }

        return path;
    }
};

int main() {
    vector<pair<string, string>> routes = {
        {"Chennai", "Hyderabad"},
        {"Hyderabad", "Bangalore"},
        {"Bangalore", "Delhi"},
        {"Hyderabad", "Delhi"}
    };

    Solution obj;

    vector<string> ans = obj.longestItinerary(routes);

    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i];

        if (i != ans.size() - 1)
            cout << " -> ";
    }

    cout << endl;

    return 0;
}