Reconstruct Itinerary

You are given a list of flight tickets where each ticket is represented as a pair of departure and arrival airport codes. Your task is to reconstruct the entire itinerary in order. The itinerary must start from JFK and use all the tickets exactly once.

If there are multiple valid itineraries, you must return the itinerary that is lexicographically smallest. Formally, if the itinerary is represented as a sequence \(\pi = [\pi_0, \pi_1, \dots, \pi_n]\), then \(\pi\) must satisfy:

\[\text{for all valid itineraries } \pi', \quad \pi \leq_{lex} \pi'\]

It is guaranteed that at least one valid itinerary exists.

inputFormat

The input is given via standard input. The first line contains a single integer (n) (the number of tickets). Each of the following (n) lines contains two strings representing the departure and arrival airport codes, separated by a space.

outputFormat

Output the reconstructed itinerary as a sequence of airport codes separated by a single space, printed to standard output.## sample

4
JFK MUC
MUC LHR
LHR SFO
SFO SJC

JFK MUC LHR SFO SJC