CF1095D.Circular Dance

There are $n$ kids, numbered from $1$ to $n$, dancing in a circle around the Christmas tree. Let's enumerate them in a clockwise direction as $p_1$, $p_2$, ..., $p_n$ (all these numbers are from $1$ to $n$ and are distinct, so $p$ is a permutation). Let the next kid for a kid $p_i$ be kid $p_{i + 1}$ if $i \lt n$ and $p_1$ otherwise. After the dance, each kid remembered two kids: the next kid (let's call him $x$) and the next kid for $x$. Each kid told you which kids he/she remembered: the kid $i$ remembered kids $a_{i, 1}$ and $a_{i, 2}$. However, the order of $a_{i, 1}$ and $a_{i, 2}$ can differ from their order in the circle.

Example: 5 kids in a circle, $p=[3, 2, 4, 1, 5]$ (or any cyclic shift). The information kids remembered is: $a_{1,1}=3$, $a_{1,2}=5$; $a_{2,1}=1$, $a_{2,2}=4$; $a_{3,1}=2$, $a_{3,2}=4$; $a_{4,1}=1$, $a_{4,2}=5$; $a_{5,1}=2$, $a_{5,2}=3$.

You have to restore the order of the kids in the circle using this information. If there are several answers, you may print any. It is guaranteed that at least one solution exists.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

有 $n$ 个孩子，编号为 $1$ 到 $n$，正围绕圣诞树顺时针围成一个圆圈跳舞。我们按顺时针方向将他们依次记为 $p_1$, $p_2$, ..., $p_n$（这些数均属于 $1$ 到 $n$ 且互不相同，因此 $p$ 是一个排列）。对于孩子 $p_i$，其“下一个孩子”定义为：若 $i \lt n$，则为 $p_{i + 1}$；否则（即 $i = n$）为 $p_1$。舞蹈结束后，每个孩子都记住了两个孩子：一个是自己的“下一个孩子”（记作 $x$），另一个是 $x$ 的“下一个孩子”。每个孩子告诉你他/她所记住的两个孩子：孩子 $i$ 记住的孩子为 $a_{i, 1}$ 和 $a_{i, 2}$。但注意，$a_{i, 1}$ 和 $a_{i, 2}$ 的顺序可能与他们在圆圈中的实际顺序不同。

示例：5 个孩子围成一圈，$p=[3, 2, 4, 1, 5]$（或其任意循环移位）。孩子们记住的信息为：$a_{1,1}=3$, $a_{1,2}=5$；$a_{2,1}=1$, $a_{2,2}=4$；$a_{3,1}=2$, $a_{3,2}=4$；$a_{4,1}=1$, $a_{4,2}=5$；$a_{5,1}=2$, $a_{5,2}=3$。

你需要根据这些信息还原孩子们在圆圈中的顺序。若存在多个合法答案，输出任意一个即可。题目保证至少存在一个解。

如果你使用 Python 编程，请在提交代码时考虑使用 PyPy 而非 Python。

The first line of the input contains one integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of the kids.

The next $n$ lines contain $2$ integers each. The $i$-th line contains two integers $a_{i, 1}$ and $a_{i, 2}$ ($1 \le a_{i, 1}, a_{i, 2} \le n, a_{i, 1} \ne a_{i, 2}$) — the kids the $i$-th kid remembered, given in arbitrary order.

输入的第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$）—— 小孩的数量。

接下来的 $n$ 行每行包含两个整数。第 $i$ 行包含两个整数 $a_{i, 1}$ 和 $a_{i, 2}$（$1 \le a_{i, 1}, a_{i, 2} \le n$，且 $a_{i, 1} \ne a_{i, 2}$）—— 表示第 $i$ 个小孩所记住的另外两个小孩的编号，顺序任意。

Print $n$ integers $p_1$, $p_2$, ..., $p_n$ — permutation of integers from $1$ to $n$, which corresponds to the order of kids in the circle. If there are several answers, you may print any (for example, it doesn't matter which kid is the first in the circle). It is guaranteed that at least one solution exists.

输出 $n$ 个整数 $p_1$, $p_2$, ..., $p_n$ —— 即 $1$ 到 $n$ 的一个排列，表示孩子们在圆圈中的顺序。若存在多个答案，可输出任意一个（例如，圆圈中谁排第一并不重要）。题目保证至少存在一个解。