Reconstruct Itinerary

You are given a list of flight tickets, each represented by a pair of departure and arrival airports. Each ticket is used exactly once to form an itinerary. The itinerary must start at JFK. If there are multiple valid itineraries, you should output the one that has the smallest lexical order when the itinerary is read as a single string. This is essentially finding an Eulerian path in a directed graph using all edges exactly once, with a lexicographical order constraint.

Note: All the tickets are provided as input. The input format gives an integer T denoting the number of tickets, followed by T lines, each containing two strings representing the departure and arrival airport codes.

The itinerary I must satisfy:

I = [JFK, a₁, a₂, ..., a_T]

where every ticket is used exactly once.

inputFormat

The first line contains an integer T which represents the number of tickets. Each of the next T lines contains two strings separated by a space, representing the departure and arrival airports respectively.

Example Input:

4
MUC LHR
JFK MUC
SFO SJC
LHR SFO

outputFormat

Output a single line containing the reconstructed itinerary. The airport codes should be separated by a single space.

Example Output:

JFK MUC LHR SFO SJC

## sample

4
MUC LHR
JFK MUC
SFO SJC
LHR SFO

JFK MUC LHR SFO SJC