← 返回题目列表

Codeforces · 263/C

C. 数字圈

中文机器翻译题面 查看原题

有一天,Vasya 走到黑板前,按照某种顺序在一个圆圈中写下了从 1 到 n 的 n 个不同的整数。然后他画弧连接整数对 (a, b) (a ≠ b),它们要么是圆中彼此的直接邻居,要么有数字 c,这样 a 和 с 是直接邻居,b 和 c 是直接邻居。您可以轻松推断出,最终 Vasya 画了 2·n 条弧。

例如,如果数字按照 1, 2, 3, 4, 5(顺时针方向)的顺序写在圆圈中,则弧将连接整数对 (1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (1, 3), (2, 4), (3, 5), (4, 1) 和 (5, 2)。

从那时起已经过去了很长时间,我们很久以前就从黑板上擦掉了这些数字,但最近 Vasya 发现了一张纸,上面写着 2·n 对整数,它们与黑板上的弧线相连。 Vasya 要求你找出这些数字在圆圈中的顺序。

输入

输入的第一行包含一个整数 n (5 ≤ n ≤ 105),显示板上写了多少个数字。接下来的 2·n 行包含整数对 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — 由弧连接的数字。

保证由弧连接的整数对在输入中不会出现多次。数字对和数字对中的数字以任意顺序给出。

输出

如果 Vasya 在某个地方犯了错误,并且没有任何方法根据语句将 1 到 n 的数字放在圆圈上,则打印一个数字“-1”(不带引号)。否则,打印从 1 到 n 的 n 个不同整数的任何合适序列。

如果有多个解决方案,您可以打印其中任何一个。具体来说,您先写哪个数字来描述订单的顺序并不重要。无论您以顺时针还是逆时针方向写出数字都没有关系。

示例

输入 #1

5
1 2
2 3
3 4
4 5
5 1
1 3
2 4
3 5
4 1
5 2

输出 #1

1 2 3 4 5

输入 #2

6
5 6
4 3
5 3
2 4
6 1
3 1
6 2
2 5
1 4
3 6
1 2
4 5

输出 #2

1 2 4 5 3 6