A traveller has a list of flight tickets. Each ticket tickets[i] = [from_i, to_i] is one flight from airport from_i to airport to_i.
The journey starts at the airport "JFK". The traveller must use every ticket exactly once. You may take it as given that at least one valid route exists.
Return the route as a list of airports, starting with "JFK". If more than one route is possible, return the smallest one. To compare two routes, find the first position where they differ and compare the airport names there as ordinary words (alphabetical order).
- For example,
["JFK", "BOM"] is smaller than ["JFK", "DEL"].
Examples
Example 1:
Input: tickets = [["JFK","BOM"],["BOM","DEL"],["DEL","JFK"]]
Output: ["JFK","BOM","DEL","JFK"]
Explanation: There is only one way to use the three tickets in a chain.
Example 2:
Input: tickets = [["JFK","DEL"],["JFK","BOM"],["BOM","JFK"]]
Output: ["JFK","BOM","JFK","DEL"]
Explanation: Going to DEL first would leave a ticket unused, so the route must go through BOM and back to JFK first.
Example 3:
Input: tickets = [["JFK","BLR"]]
Output: ["JFK","BLR"]
Explanation: One ticket gives a route of two airports.