class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = self.build_graph(tickets)
        self.ans = []
        self.dfs(graph, 'JFK')

        return self.ans[::-1]

    def build_graph(self, tickets):
        graph = collections.defaultdict(list)
        for _from, _to in tickets:
            graph[_from].append(_to)

        for _from in graph:
            graph[_from].sort(reverse = True)
            # dfs get reverse lexical order (since we get ans from end to start)           

        return graph

    def dfs(self, graph, _from):
        # end of recursion, when find no route
        while graph[_from]:
            # define and split
            self.dfs(graph, graph[_from].pop())

        # append ans, from end to start
        self.ans.append(_from)