Lexicographically smallest itinerary

Write codeHard35 minGoogle and Amazon style

Your task

You have a list of one-way flight tickets [from, to] (airport codes). Reconstruct an itinerary that uses every ticket exactly once and starts at 'JFK'. It is guaranteed at least one valid itinerary exists. If multiple are possible, return the one that is lexicographically smallest when read as a list of airport codes. Return the itinerary as a list of airport codes in visiting order.

Examples

reconstruct_itinerary(tickets: list[list[str]]) -> list[str]

Example 1

Inputreconstruct_itinerary([["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]])

Output["JFK", "MUC", "LHR", "SFO", "SJC"]