Circle of Numbers

题意翻译

## 题目描述 有一天，Vasya走到黑板前，把 $1$ 到 $n$ 之间的不同整数按一定的顺序画成一个圆圈。然后他画弧来连接整数对 $(a,b)\ (a≠b)$，它们要么在圆相邻，要么有数字 $c$，使得 $a$ 和 $c$ 相邻，并且 $b$ 和 $c$ 相邻。易得出，瓦西亚最后画了 $2n$ 条弧。 例如，如果将数字 $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 发现了一张纸，上面写着 $2n$ 个整数对，它们对应着原来黑板上的每个圆弧相联的数对。Vasya 要求您通过这些数对查找圆圈中原有的数字顺序。 ## 输入格式 输入的第一行包含一个整数 $n ( 5 \le n \le 10^5 ) $。这表明，黑板上写了多少个数字。接下来的2.n行包含整数对 $a_i,b_i\ ( 1 \le a_i,b_i \le n \ , a_i \not = b_i )$ ——由弧连接的数字。 可以保证输入中不会出现由圆弧连接的一对整数超过一次。 数字对和其中的数字按任意顺序给出。 ## 输出格式 输出从 $1$ 到 $n$ 的 $n$ 个不同整数的任意合适序列，若无法根据题意将 $1$ 到 $n$ 之间的数字放在圆圈上，则输出 $"- \! 1"$ （不包括引号）。 如果有多个解决方案，则允许输出其中任何一个。具体来说，先写哪个数字来描述顺序并不重要。无论你是顺时针还是逆时针写数字，这也无关紧要。

题目描述

One day Vasya came up to the blackboard and wrote out $ n $ distinct integers from $ 1 $ to $ n $ in some order in a circle. Then he drew arcs to join the pairs of integers $ (a,b) $ $ (a≠b) $ , that are either each other's immediate neighbors in the circle, or there is number $ c $ , such that $ a $ and $ с $ are immediate neighbors, and $ b $ and $ c $ are immediate neighbors. As you can easily deduce, in the end Vasya drew $ 2·n $ arcs. For example, if the numbers are written in the circle in the order $ 1,2,3,4,5 $ (in the clockwise direction), then the arcs will join pairs of integers $ (1,2) $ , $ (2,3) $ , $ (3,4) $ , $ (4,5) $ , $ (5,1) $ , $ (1,3) $ , $ (2,4) $ , $ (3,5) $ , $ (4,1) $ and $ (5,2) $ . Much time has passed ever since, the numbers we wiped off the blackboard long ago, but recently Vasya has found a piece of paper with $ 2·n $ written pairs of integers that were joined with the arcs on the board. Vasya asks you to find the order of numbers in the circle by these pairs.

输入输出格式

输入格式

The first line of the input contains a single integer $ n $ ( $ 5<=n<=10^{5} $ ) that shows, how many numbers were written on the board. Next $ 2·n $ lines contain pairs of integers $ a_{i} $ , $ b_{i} $ ( $ 1<=a_{i},b_{i}<=n $ , $ a_{i}≠b_{i} $ ) — the numbers that were connected by the arcs. It is guaranteed that no pair of integers, connected by a arc, occurs in the input more than once. The pairs of numbers and the numbers in the pairs are given in the arbitrary order.

输出格式

If Vasya made a mistake somewhere and there isn't any way to place numbers from $ 1 $ to $ n $ on the circle according to the statement, then print a single number "-1" (without the quotes). Otherwise, print any suitable sequence of $ n $ distinct integers from $ 1 $ to $ n $ . If there are multiple solutions, you are allowed to print any of them. Specifically, it doesn't matter which number you write first to describe the sequence of the order. It also doesn't matter whether you write out the numbers in the clockwise or counter-clockwise direction.

输入输出样例

输入样例 #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