Lexicographically Smallest Itinerary

Given a list of flights represented as pairs of airport codes and a starting airport, your task is to construct an itinerary that uses all the flights exactly once. The itinerary must be the lexicographically smallest possible.

Formally, you are given a list of flights where each flight is denoted by a pair of strings, representing the departure and arrival airports. You have to find an itinerary that starts at a given airport and uses each flight exactly once. If there are multiple valid itineraries, choose the one that is lexicographically smallest. The lexicographical order is determined by the natural string order.

You can model the problem as finding an Eulerian path in a directed graph. A useful fact in such problems is that the lexicographically smallest Eulerian path can be computed using a variant of Hierholzer's algorithm with a priority queue (or sorting of neighbors). In mathematical notation, if S is the starting airport and F is the set of flights, you need to find a sequence of airports A = [a_0, a_1, \dots, a_n] such that:

[ a_0 = S, \quad \text{and} \quad {(a_i, a_{i+1}) : 0 \le i < n} = F, ]

and if there exists another valid itinerary B, then A is lexicographically smaller than B.

inputFormat

The first line contains a single integer n indicating the number of flights.

The following n lines each contain two strings separated by a space representing a flight from a departure airport to an arrival airport.

The last line contains a single string representing the starting airport.

Example:

3
JFK KUL
JFK NRT
NRT JFK
JFK

outputFormat

Output a single line listing the itinerary as a sequence of airport codes separated by spaces.

Example:

JFK NRT JFK KUL

## sample

3
JFK KUL
JFK NRT
NRT JFK
JFK

JFK NRT JFK KUL

</p>