class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        g = collections.defaultdict(dict)
        for u,v in tickets:
            if v not in g[u]:
                g[u][v] = 0
            g[u][v] += 1
        print(g)
        
        
        res = None
        def dfs(g, curr, path):
            
            nonlocal res
            
            if res :
                return
            
            if len(path) == len(tickets) + 1:
                res = path[:]
            
            for neighbor in sorted(g[curr].keys()):
                
                if g[curr][neighbor] == 0:
                    continue
                
                g[curr][neighbor]-=1
                path.append(neighbor)
                
                dfs(g, curr = neighbor, path = path)
                
                g[curr][neighbor] += 1
                path.pop()
            
        dfs(g, "JFK", ['JFK'])
        return res