← 返回题目列表

AtCoder · typical90_bj

062. 全部涂漆(★6)

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

配点: 6 点

問題文

N 白球和 有 N 项。每个球和物品都有 1 减去 N 。
这里,该项目 以下是关于 i 的已知信息。

  • 球 A_i, B_i 的至少一方是白色时,以及仅在那时可以使用。
  • 使用这个,可以将球 i 涂成黑色。

N 个物品,是否可以将所有球涂成黑色。
如果可能,请提供使用顺序的一个示例。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq A_i, B_i \leq N
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

如果无法将所有的球涂成黑色,-1 ,否则输出
如果可能的话,请按以下格式输出。

X_1
X_2
\vdots
X_N

X_i 是 您也可以写 i 表示要使用的第几个物品的编号。
在这里,1 \le X_i \le N, X_i \neq X_j\ (i \neq j) 和 X_i 必须全部是整数。

如果物品使用顺序有多种可能,可以输出其中任何一种。


入力例 1

4
3 4
1 3
2 3
2 1

出力例 1

4
2
1
3

下面的输出示例表示这是正确的输出:

  1. 球 2\ (=A_4) 和球 1\ (=B_4) 因为是白色的物品 4 使得球 4 涂成黑色。
  2. 球 1\ (=A_2) 和球 3\ (=B_2) 因为是白色的物品 2 使得球 2 涂成黑色。
  3. 球 4\ (=B_1) 是黑色的,但由于球 3\ (=A_1) 是白色的,所以物品 1 使得球 1 涂成黑色。
  4. 球 2\ (=A_3) 是黑色的,但由于球 3\ (=B_3) 是白色的,所以物品 3 使得球 3 涂成黑色。

就这样把所有的球都染成了黑色。请注意,即使操作后 A_i,B_i 都变成黑色,也没关系,关键是在操作前其中一个是白色的。也可以按

此外,4,1,2,3 的顺序使用物品。


入力例 2

3
1 1
2 2
3 3

出力例 2

3
2
1

无论以何种顺序使用物品都可以。

另外,在这个问题中 A_i = B_i 请注意可能会出现的情况。


入力例 3

5
3 4
4 5
1 1
5 1
3 2

出力例 3

-1

无论如何,都无法将所有球涂成黑色。


入力例 4

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

出力例 4

1
5
3
6
4
2

这个输出例是唯一的正确答案。


入力例 5

10
5 1
3 9
7 8
9 3
3 7
10 10
3 5
4 7
1 1
6 6

出力例 5

-1