配点: 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
下面的输出示例表示这是正确的输出:
- 球 2\ (=A_4) 和球 1\ (=B_4) 因为是白色的物品 4 使得球 4 涂成黑色。
- 球 1\ (=A_2) 和球 3\ (=B_2) 因为是白色的物品 2 使得球 2 涂成黑色。
- 球 4\ (=B_1) 是黑色的,但由于球 3\ (=A_1) 是白色的,所以物品 1 使得球 1 涂成黑色。
- 球 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