Riding Fences

Problem Background

Special for beginners, ^_^

Problem Description

Farmer John has many fences to repair every year. He always rides his horse through every fence and fixes the broken parts.

John is as lazy as any other farmer. He hates riding, so he never passes the same fence twice. You must write a program that reads the description of the fence network and computes a path to repair the fences such that every fence is traversed exactly once. John may start riding from any vertex (the intersection of two fences) and finish at any vertex.

Each fence connects two vertices, labeled from $1$ to $500$ (although some farms may not have $500$ vertices). Any number ($\ge 1$) of fences may meet at a single vertex. All fences are connected (that is, you can reach any fence from any other fence).

Your program must output the riding path (represented by the vertex numbers visited in order along the path). If we view the output path as a number in base $500$, then when multiple solutions exist, output the one that is smallest in this base-$500$ representation (i.e. output the one with the smaller first number; if there is still a tie, the one with the smaller second number, and so on). The input guarantees at least one solution.

Input Format

The first line: an integer $F$ ($1 \le F \le 1024$), the number of fences.

Lines $2$ to $F+1$: each line contains two integers $i, j$ ($1 \le i, j \le 500$) indicating that this fence connects vertex $i$ and vertex $j$.

Output Format

The output should have $F+1$ lines, each containing one integer, representing the vertex numbers along the path in order. Note that there may be multiple solutions, but only the one required by the statement above is considered correct.

Sample Input

9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6

Sample Output

1
2
3
4
2
5
4
6
5
7

Hint

The graph is not necessarily simple; there may be multiple edges between two vertices.

Constraints

Time limit: 1s; memory limit: 1024 KiB for each test case.