## Problem You are given airline tickets where each ticket `[from, to]` must be used exactly once. Reconstruct an itinerary that starts at `"JFK"`. When more than one complete itinerary exists, return the lexicographically smallest sequence of airport codes. ### Function Contract Implement `reconstructItinerary(tickets)` and return the airport sequence, including the starting airport. ### Constraints & Assumptions - `1 <= len(tickets) <= 300,000`. - Each airport code is a nonempty ASCII string. - Duplicate tickets are distinct and must each be used. - The input guarantees at least one itinerary using every ticket from `"JFK"`. - Lexicographic comparison uses the airport-code strings. ### Clarifying Questions to Ask - Must every ticket be used? Yes, exactly once. - May the graph contain cycles and duplicate edges? Yes. - Is a greedy choice of the smallest immediate destination always safe? No; it may strand unused tickets. - What determines the answer among valid itineraries? The lexicographically smallest full airport sequence. ```hint Think in edges, not visited airports This is an Eulerian trail problem; visiting an airport does not consume all routes through it. ``` ```hint Append after exhausting choices Repeatedly take the smallest remaining outgoing ticket, and add an airport to the result only after it has no outgoing tickets left. ``` ### Example ```text tickets = [["JFK","SFO"], ["JFK","ATL"], ["SFO","ATL"], ["ATL","JFK"], ["ATL","SFO"]] output = ["JFK","ATL","JFK","SFO","ATL","SFO"] ``` ### Evaluation Focus - Uses each ticket occurrence exactly once. - Handles cycles, duplicate tickets, and temporary dead ends. - Enforces lexical order without exponential backtracking. - Runs in `O(e log e)` time or `O(e log d)` with per-airport heaps. ### Extensions to Discuss 1. Why does postorder reversal repair an apparently premature dead end? 2. How would you validate that a complete itinerary exists? 3. How would the answer change if the starting airport were not fixed?