1063. Reconstruct Itinerary (Eulerian Path)

Given a list of airline tickets [from, to], reconstruct the itinerary that uses all tickets exactly once, starting from 'JFK'. If multiple valid itineraries exist, return the one with the smallest lexical order when read as a single list of airports. A valid itinerary is guaranteed. The input is JSON {tickets}.

Input: JSON {tickets}.

Output: Array — the airport sequence.

Examples

Input: {"tickets":[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]}
Output: ["JFK","MUC","LHR","SFO","SJC"]
Explanation: Uses every ticket from JFK.

Input: {"tickets":[["JFK","A"],["A","JFK"]]}
Output: ["JFK","A","JFK"]
Explanation: Round trip.

Input: {"tickets":[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]}
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Lexically smallest Eulerian path.

Constraints

• 1<=tickets<=300

Asked by