Description

John is as lazy as any other farmer. He hates riding, so he never goes along the same fence twice.

There are $m$ fences on John’s farm. Each fence connects two vertices, and vertices are labeled from $1$ to $500$ (though a given farm may have fewer vertices). At each vertex at least $1$ fence meets, with no upper bound. There may be multiple fences between the same pair of vertices. The fence graph is connected (i.e., you can reach any fence from any other fence). John may start riding at any vertex (i.e., an intersection point of fences) and finish at any vertex.

You need to output a riding route (represented by the sequence of vertex labels encountered along the way) such that each fence is traversed exactly once. If multiple valid routes exist, apply the following rule: if you view the output path as a base-$500$ number, then among all possible routes, output the smallest one in base-$500$ representation (that is, minimize the first entry; if still tied, minimize the second entry; and so on).

The input guarantees that there is at least one solution.

Input Format

The first line contains an integer $m$, the number of fences.

From the second line to the $(m+1)$-th line, each line contains two integers $u, v$, indicating there is a fence connecting vertices $u$ and $v$.

Output Format

Output $(m+1)$ lines. Each line contains one integer, the vertex label of the route in order. Note that there may be multiple solutions, but only the one specified above is considered correct.

The input guarantees that there is at least one valid solution.

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

1
2
3
4
2
5
4
6
5
7

Hint

For $100\%$ of the testdata, $1 \leq m \leq 1024, 1 \leq u, v \leq 500$.

Problem translation from NOCOW.

USACO Training Section 3.3.

Translated by ChatGPT 5