Reconstruct Itinerary

Order all tickets into one itinerary starting at JFK, using every ticket exactly once and choosing the lexicographically smallest path (Hierholzer / Eulerian path). Problem Requirements You are given a list of airline tickets. Each ticket shows where a flight starts and where it ends, written as [from, to]. Your task is to arrange these flights in the correct order to build a complete travel plan. Here are the rules you must follow: Start Point: The traveler always starts at "JFK". Your path must begin there. Order: If there is more than one valid way to arrange the flights, choose the path that comes first alphabetically (smallest lexical order). Example: A path going to ["JFK", "LGA"] is chosen over ["JFK", "LGB"] because "LGA" comes before "LGB". Validity: You can assume that a valid path always exists. Usage: You must use every single ticket exactly once. Sample Inputs and Outputs Example 1: Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] Output: ["JFK","MUC","LHR","SFO","SJC"] Example 2: Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] Output: ["JFK","ATL","JFK","SFO","ATL","SFO"] Explanation: We chose the first itinerary because "ATL" is alphabetically smaller than "SFO". Therefore, we visit "ATL" before "SFO" when leaving "JFK" for the first time. Technical Limits List Size: There are between 1 and 300 tickets. Ticket Size: Each ticket contains exactly 2 items (origin and destination). Code Length: Airport codes are exactly 3 characters long. Characters: Airport codes use only uppercase English letters. Movement: The departure airport is never the same as the arrival airport (from is not to). Interview Follow-Up Question Challenge: How would you change your solution if you needed to return all possible valid itineraries, rather than just the one that comes first alphabetically?