Reconstruct Itinerary

You are given flight tickets as [from, to] pairs and a starting airport. Every ticket must be used exactly once. Reconstruct the full itinerary; if several are valid, return the lexicographically smallest one as a list of airports.

tickets = [["MUC","LHR"], ["JFK","MUC"], ["SFO","SJC"], ["LHR","SFO"]], start = "JFK"
=> ["JFK", "MUC", "LHR", "SFO", "SJC"]

tickets = [["JFK","SFO"], ["JFK","ATL"], ["SFO","ATL"], ["ATL","JFK"], ["ATL","SFO"]], start = "JFK"
=> ["JFK", "ATL", "JFK", "SFO", "ATL", "SFO"]

The follow-up that fails candidates

Does the itinerary contain a loop? — that is, does it ever revisit an airport it has already been through? Implement hasLoop(tickets, start) for the same inputs.

Also be ready for

• The start airport isn't given: find the airport with out-degree = in-degree + 1, else any airport on the circuit.
• The tickets may not form a valid itinerary at all: validate before walking.

Up to 300 tickets; airport codes are three uppercase letters.