from collections import defaultdict, deque
from typing import List

def findItinerary(tickets: List[List[str]]) -> List[str]:
    graph = defaultdict(list)
    for frm, to in tickets:
        graph[frm].append(to)
    # sort and convert to deque for efficient popleft
    for k in graph:
        graph[k].sort()
        graph[k] = deque(graph[k])

    path = []
    def dfs(curr: str):
        dest = graph.get(curr, deque())
        while dest:
            nxt = dest.popleft()
            dfs(nxt)
        path.append(curr)

    dfs("JFK")
    return path[::-1]
            

import java.util.*;

public class Solution {
    public List findItinerary(List> tickets) {
        Map> graph = new HashMap<>();
        for (List t : tickets) {
            graph.computeIfAbsent(t.get(0), k -> new LinkedList<>()).add(t.get(1));
        }
        // sort each adjacency list and turn into a LinkedList (so we can removeFirst)
        for (Map.Entry> e : graph.entrySet()) {
            List list = e.getValue();
            Collections.sort(list);
            e.setValue(new LinkedList<>(list));
        }

        List path = new ArrayList<>();
        dfs("JFK", graph, path);
        Collections.reverse(path);
        return path;
    }

    private void dfs(String curr, Map> graph, List path) {
        LinkedList dest = graph.get(curr);
        while (dest != null && !dest.isEmpty()) {
            String next = dest.removeFirst();
            dfs(next, graph, path);
        }
        path.add(curr);
    }
}
     

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

vector findItinerary(vector>& tickets) {
    unordered_map> graph;
    for (auto &t : tickets) {
        graph[t[0]].push_back(t[1]);
    }
    // sort destinations lexicographically ascending
    for (auto &p : graph) sort(p.second.begin(), p.second.end());

    vector path;
    function dfs = [&](const string &curr) {
        auto &dest = graph[curr];
        while (!dest.empty()) {
            string next = dest.front();
            dest.erase(dest.begin()); // remove from front
            dfs(next);
        }
        path.push_back(curr);
    };

    dfs("JFK");
    reverse(path.begin(), path.end());
    return path;
}
    

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MAX_NODES 1000
#define MAX_TICKETS 10000
#define MAX_STR_LEN 64
// adjacency list storage
char *adj[MAX_NODES][MAX_TICKETS];
int adjCount[MAX_NODES];

char nodes[MAX_NODES][MAX_STR_LEN];
int nodeCount = 0;

int find_or_add_node(const char *s) {
    for (int i = 0; i < nodeCount; ++i)
        if (strcmp(nodes[i], s) == 0) return i;
    if (nodeCount >= MAX_NODES) { fprintf(stderr, "node limit\n"); exit(1); }
    strncpy(nodes[nodeCount], s, MAX_STR_LEN-1);
    nodes[nodeCount][MAX_STR_LEN-1] = '\0';
    adjCount[nodeCount] = 0;
    return nodeCount++;
}

int cmp_strptr(const void *a, const void *b) {
    const char *const *pa = a;
    const char *const *pb = b;
    return strcmp(*pa, *pb);
}

char *path[MAX_TICKETS + MAX_NODES];
int pathLen = 0;

void dfs(int u) {
    while (adjCount[u] > 0) {
        // pop front: take adj[u][0], then shift remaining left
        char *next = adj[u][0];
        // shift left
        for (int i = 1; i < adjCount[u]; ++i)
            adj[u][i-1] = adj[u][i];
        adjCount[u]--;
        // find index of next node
        int v = -1;
        for (int i = 0; i < nodeCount; ++i)
            if (strcmp(nodes[i], next) == 0) { v = i; break; }
        if (v == -1) { fprintf(stderr, "node not found\n"); exit(1); }
        dfs(v);
    }
    path[pathLen++] = strdup(nodes[u]);
}

int main() {
    // Example input: you can replace this with dynamic input parsing.
    // Here we hardcode a few tickets for demonstration.
    const char *tickets[][2] = {
        {"MUC","LHR"},
        {"JFK","MUC"},
        {"SFO","SJC"},
        {"LHR","SFO"}
    };
    int ticketCount = 4;

    // build graph
    for (int i = 0; i < ticketCount; ++i) {
        int a = find_or_add_node(tickets[i][0]);
        int b = find_or_add_node(tickets[i][1]);
        adj[a][adjCount[a]++] = strdup(tickets[i][1]);
    }

    // sort adjacency lists lexicographically
    for (int i = 0; i < nodeCount; ++i) {
        if (adjCount[i] > 0) {
            qsort(adj[i], adjCount[i], sizeof(char*), cmp_strptr);
        }
    }
    // find index of "JFK"
    int start = -1;
    for (int i = 0; i < nodeCount; ++i) {
        if (strcmp(nodes[i], "JFK") == 0) { start = i; break; }
    }
    if (start == -1) {
        printf("No JFK start\n");
        return 0;
    }

    dfs(start);

    // reverse and print
    for (int i = pathLen - 1; i >= 0; --i) {
        printf("%s", path[i]);
        if (i) printf(" -> ");
    }
    printf("\n");
    for (int i = 0; i < pathLen; ++i) free(path[i]);
    for (int i = 0; i < nodeCount; ++i)
        for (int j = 0; j < adjCount[i]; ++j)
            free(adj[i][j]);
    return 0;
}
            

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList FindItinerary(IList> tickets) {
        var graph = new Dictionary>();
        foreach (var t in tickets) {
            var from = t[0];
            var to = t[1];
            if (!graph.ContainsKey(from)) graph[from] = new LinkedList();
            graph[from].AddLast(to);
        }

        // sort each adjacency list lexicographically
        var keys = graph.Keys.ToList();
        foreach (var k in keys) {
            var sorted = graph[k].OrderBy(s => s).ToList();
            graph[k] = new LinkedList(sorted);
        }

        var path = new List();
        Dfs("JFK", graph, path);
        path.Reverse();
        return path;
    }
    private void Dfs(string curr, Dictionary> graph, List path) {
        if (!graph.ContainsKey(curr)) {
            path.Add(curr);
            return;
        }
        var dest = graph[curr];
        while (dest.Count > 0) {
            var next = dest.First.Value;
            dest.RemoveFirst();
            Dfs(next, graph, path);
        }
        path.Add(curr);
    }
}