CF1095D Circular Dance

有 $n$ 个小朋友，编号从 $1$ 到 $n$，他们围着圣诞树顺时针跳舞。我们顺时针依次编号为 $p_1$、$p_2$、…、$p_n$（这些数字都是 $1$ 到 $n$ 的不同整数，因此 $p$ 是一个排列）。对于小朋友 $p_i$，下一个小朋友是 $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。

输入的第一行包含一个整数 $n$（$3 \le n \le 2 \times 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$ 个小朋友记住的两个小朋友，顺序任意。

输出 $n$ 个整数 $p_1$、$p_2$、…、$p_n$，表示小朋友们在圈中的顺序，是 $1$ 到 $n$ 的一个排列。如果有多种答案，可以输出任意一种（例如，圈中第一个小朋友是谁并不重要）。保证至少存在一种解。

由 ChatGPT 4.1 翻译