1
class Solution:
2
    def findTicketsAdjList(self, tickets):
3
        ticket = {}
4
        for src, dest in tickets:
5
            if src in ticket:
6
                ticket[src].append(dest)
7
            else:
8
                ticket[src] = [dest]
9

10
        for src, dest in ticket.items():
11
            if len(dest) > 1:
12
                ticket[src] = sorted(ticket[src], reverse=True)
13

14
        return ticket
15

16
    def reconstructItinerary(self, source, tickets, itinerary):
17
        if source in tickets:
18
            while tickets[source]:
19
                destination = tickets[source].pop()
20
                self.reconstructItinerary(destination, tickets, itinerary)
21
        itinerary.append(source)
22
        return itinerary
23

24
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
25
        if len(tickets) == 1:
26
            if "JFK" not in tickets[0]:
27
                return []
28

29
        ticketsAdj = self.findTicketsAdjList(tickets)
30
        if "JFK" not in ticketsAdj:
31
            return []
32
        itinerary = []
33
        itinerary = self.reconstructItinerary("JFK", ticketsAdj, itinerary)
34

35
        return itinerary[::-1]