Lexicographically Smallest Eulerian Path

John is as lazy as any other farmer. He hates riding horses and therefore never rides through the same fence twice. On John's farm, there are \(m\) fences; each fence connects two vertices whose labels range from \(1\) to \(500\) (even though some farms may have fewer vertices). Each vertex is connected to at least one fence (with no upper limit) and there may be multiple fences connecting the same pair of vertices. Moreover, all fences form a connected structure (i.e. you can reach any fence from any other fence).

John can start his ride at any vertex (the intersection point of two fences) and can end at any vertex. Your task is to output a riding path—represented by the sequence of vertex numbers visited in order—for which every fence is traversed exactly once. This is equivalent to finding an Eulerian path in the undirected multigraph.

If there are multiple valid Eulerian paths, consider the output path as a number in base \(500\) (where each vertex represents a digit) and output the smallest one. In other words, when comparing two solutions lexicographically, select the one with the smallest first vertex; if there is a tie, compare the second vertex; and continue similarly.

It is guaranteed that at least one valid path exists.

inputFormat

The first line contains an integer \(m\), representing the number of fences. The following \(m\) lines each contain two space-separated integers \(u\) and \(v\), indicating that there is a fence connecting vertex \(u\) and vertex \(v\).

outputFormat

Output the Eulerian path as a sequence of vertex numbers separated by spaces.

sample

3
1 2
2 3
1 3

1 2 3 1