Reconstruct Itinerary

hardAdvanced GraphsEulerian path (Hierholzer's) with lexical orderingSolve on LeetCode#332

You are given a stack of plane tickets, each a pair [from, to] of three-letter airport codes. Starting from "JFK", build a trip that uses every ticket exactly once, and return the ordered list of airports visited. If more than one complete trip exists, return the one that reads smallest in dictionary order when the airports are compared one by one. The input is guaranteed to allow at least one valid trip.

Constraints that matter: up to 300 tickets, and duplicate tickets between the same pair of airports are allowed — so track ticket counts, not just connections.

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"]

["JFK","SFO","ATL","JFK","ATL","SFO"] also uses every ticket, but it starts JFK → SFO while the answer starts JFK → ATL, and "ATL" comes before "SFO" alphabetically.

Hints

One at a time — struggle first, peek second.

Your thinking space — verify on LeetCode, then mark it.