Reconstruct Itinerary

Consume tickets with Hierholzer's algorithm

Build an adjacency list from each airport to its destinations in reverse lexical order, or use a min-heap. DFS from the required start airport. While an outgoing ticket remains, remove one destination and recurse. Append the current airport only after all its outgoing edges are consumed, then reverse the collected list. Postorder is essential: a locally smallest flight can be a dead end until its cycle is resolved. The invariant is that every removed edge is used once and an airport is added only when no unused outgoing edge can extend its current tour. Sorting costs O(E log E) and traversal is O(E); storage is O(E). Test duplicate tickets, cycles, lexical choices, and a route whose valid continuation must be spliced back into an earlier airport.