有$$$n$$$个孩子,编号从$$$1$$$到$$$n$$$,围着圣诞树跳舞。让我们按顺时针方向将它们枚举为$$$p_1$$$,$$$p_2$$$,...,$$$p_n$$$(所有这些数字都从$$$1$$$到$$$n$$$并且是不同的,因此$$$p$$$是一个排列)。如果 $$$i < n$$$,则让孩子 $$$p_i$$$ 的下一个孩子为孩子 $$$p_{i + 1}$$$,否则为 $$$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 \cdot 10^5$$$) — 孩子的数量。
接下来的 $$$n$$$ 行每行包含 $$$2$$$ 个整数。第 $$$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$$$ 的整数排列,对应于圆圈中孩子的顺序。如果有多个答案,您可以打印任何一个(例如,哪个孩子是圈中的第一个并不重要)。保证至少存在一个解。
示例
输入 #1
5 3 5 1 4 2 4 1 5 2 3
输出 #1
3 2 4 1 5
输入 #2
3 2 3 3 1 1 2
输出 #2
3 1 2