Given a list of airline tickets represented by departure and arrival airports, reconstruct the itinerary in lexical order.
All trips begin at JFK.
Examples
Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] Output: ["JFK","MUC","LHR","SFO","SJC"]
Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Constraints
- 1 <= tickets.length <= 300
- All airports are three uppercase letters.