Problem B
Oriented Traversal

An oriented traversal of a polygon is the sequence of its corner labels in the order encountered when one starts at some corner and follows the boundary in a fixed direction until returning to the start.

You are given a simple polygon with $n$ corners. The corners are labeled $1,\dots ,n$, but—unlike what you might expect—these labels are not necessarily in oriented traversal order. Instead, the input consists of an unordered collection of $n$ distinct line segments, which together form the boundary of the polygon.

Each line segment connects two corners, written as an unordered pair $\{ a_i,b_i\} $ for $i\in \{ 1,\ldots ,n\} $. Your task is to list the corners in oriented traversal order, that is, the order they appear in when the chain is traversed all the way around once, starting and ending at corner $1$. In particular, each consecutive pair of corners in your list should form one of the given segments. Note that a segment $\{ a_i,b_i\} $ can be used to traverse from $a_i$ to $b_i$ or from $b_i$ to $a_i$.

For example, the four line segments $\{ 1,2\} $, $\{ 1,3\} $, $\{ 2,4\} $, and $\{ 3,4\} $ form a closed polygonal chain, and traversing the boundary, we obtain the oriented traversal $1,2,4,3,1$. Similarly, the six line segments $\{ 1,4\} $, $\{ 1,5\} $, $\{ 2,3\} $, $\{ 2,5\} $, $\{ 3,6\} $, and $\{ 4,6\} $ form a closed polygonal chain, leading to the oriented traversal $1$, $4$, $6$, $3$, $2$, $5$, $1$. We can illustrate these examples as shown below, where the corners would have been traversed counterclockwise, but note that the geometric shape of the polygons and the rotational direction is actually irrelevant for your task:

To be quite formal, the task is to find an ordering $p_1, p_2, \ldots , p_n, p_1$ of the corner points with $p_1=1$ such that the following holds:

Input

The input consists of:

• One line with an integer $n\in \{ 3,\ldots ,100\, 000\} $, the number of line segments.

• $n$ lines, one for each segment. The $i$th line contains the corners $a_i$ and $b_i$ with $1\leq a_i<b_i\leq n$. The segments are given in arbitrary order. Every corner occurs exactly twice.

Output

Write the corners of the closed polygonal chain in oriented traversal order, starting and ending with $1$. If there are multiple valid solutions you may output any one of them.

4
1 2
2 4
1 3
3 4

1 2 4 3 1

6
1 4
1 5
2 3
2 5
3 6
4 6

1 4 6 3 2 5 1