class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {

        // 构建邻接表
        for(const auto& ticket: tickets) {
            trip[ticket[0]].push_back(ticket[1]);
        }

        // 邻接表按字典序排序
        for(auto& pair: trip) {
            auto& dest = pair.second;
            sort(dest.begin(), dest.end());
        }

        const string start = "JFK";  // 开始顶点

        dfs(start);

        return vector<string>(route.crbegin(), route.crend());
    }

private:
    unordered_map<string, deque<string>> trip; // 邻接表
    vector<string> route; // 所求路径的倒置

    void dfs(const string& src) {
        auto& dests = trip[src];
        while(!dests.empty()) {
            const string dest = dests.front();
            dests.pop_front();
            dfs(dest);
        }
        route.push_back(src);
    }
};