class Solution(object):
    def findItinerary(self, tickets):
        graph = collections.defaultdict(dict)
        for u, v in tickets:
            graph[u][v] = graph[u].get(v, 0) + 1

        def search(node, path):
            if len(path) == len(tickets) + 1:
                return path
            for nei in sorted(graph[node]):
                if graph[node][nei]:
                    graph[node][nei] -= 1
                    ans = search(nei, path + [nei])
                    if ans: return ans
                    graph[node][nei] += 1

        return search('JFK', ['JFK'])