class Solution {
    
    public LinkedList<String> ans = new LinkedList<>();
    public HashMap<String , PriorityQueue<String>> graph = new HashMap<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        /* Q32 of graph playlist , eularian path and circuit , 

            we have to use every ticket once or every edge once which is a eularian path .
            
            1)make graph of HM<string , PQ<string>>
            2)fire DFS
            3)add nodes while backtracking in linkedlist int addfirst manner 

            -> LL is used as addfirst in LL is O(1)
        */

        //making graph
        for(List<String> nodes : tickets){
            String a = nodes.get(0) , b = nodes.get(1);

            graph.computeIfAbsent(a , k -> new PriorityQueue<>()).add(b);
        }

        //firing DFS
        DFS("JFK");
        return ans;
    }

    public void DFS(String source){

        PriorityQueue<String> pq = graph.get(source);

        //might be that PQ of some node is not even initiallized therefore check for null
        //going to neighours
        while(pq != null && pq.size() > 0){
            String nbrs = pq.remove();
            DFS(nbrs);
        }

        //adding nodes while backtracking
        ans.addFirst(source);
    }
}