← 返回题目列表

Codeforces · 1152/E

E. Neko 和闪回

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

长度 $$$k$$$ 的排列是从 $$$1$$$ 到 $$$k$$$ 的 $$$k$$$ 整数序列,每个整数只包含一次。例如,序列 $$$[3, 1, 2]$$$ 是长度 $$$3$$$ 的排列。

当 Neko 五岁的时候,他想到了一个由 $$$n$$$ 正整数组成的数组 $$$a$$$ 和一个长度为 $$$n - 1$$$ 的排列 $$$p$$$。然后,他执行了以下操作:

- 构造了一个长度为 $$$n-1$$$ 的数组 $$$b$$$,其中 $$$b_i = \min(a_i, a_{i+1})$$$。
- 构造了一个长度为 $$$n-1$$$ 的数组 $$$c$$$,其中 $$$c_i = \max(a_i, a_{i+1})$$$。
- 构造了一个长度为 $$$n-1$$$ 的数组 $$$b'$$$,其中 $$$b'_i = b_{p_i}$$$。
- 构造了一个长度为 $$$n-1$$$ 的数组 $$$c'$$$,其中 $$$c'_i = c_{p_i}$$$。

例如,如果数组 $$$a$$$ 是 $$$[3, 4, 6, 5, 7]$$$ 并且排列 $$$p$$$ 是 $$$[2, 4, 1, 3]$$$,那么 Neko 将构建以下数组:

- $$$b = [3, 4, 5, 5]$$$
- $$$c = [4, 6, 6, 7]$$$
- $$$b' = [4, 5, 3, 5]$$$
- $$$c' = [6,7,4,6]$$$

然后,他在一张纸上写下了两个数组$$$b'$$$和$$$c'$$$,然后就忘记了。 14年后,当他清理房间时,他发现了这张旧纸,上面写着两个数组$$$b'$$$和$$$c'$$$。然而他不记得他使用的数组 $$$a$$$ 和排列 $$$p$$$ 。

如果 Neko 犯了一个错误,并且没有数组 $$$a$$$ 和排列 $$$p$$$ 导致这样的 $$$b'$$$ 和 $$$c'$$$,则打印 -1。否则,帮助他恢复任何可能的数组$$$a$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — 数组 $$$a$$$ 中的元素数量。

第二行包含 $$$n-1$$$ 整数 $$$b'_1, b'_2, \ldots, b'_{n-1}$$$ ($$$1 \leq b'_i \leq 10^9$$$)。

第三行包含 $$$n-1$$$ 整数 $$$c'_1, c'_2, \ldots, c'_{n-1}$$$ ($$$1 \leq c'_i \leq 10^9$$$)。

输出

如果 Neko 犯了一个错误,并且没有数组 $$$a$$$ 和导致 $$$b'$$$ 和 $$$c'$$$ 的排列 $$$p$$$,则打印 -1。否则,打印 $$$n$$$ 正整数 $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$),表示数组 $$$a$$$ 的元素。

如果有多种可能的解决方案,请打印其中任何一个。

示例

输入 #1

5
4 5 3 5
6 7 4 6

输出 #1

3 4 6 5 7

输入 #2

3
2 4
3 2

输出 #2

-1

输入 #3

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

输出 #3

3 4 5 2 1 4 3 2

注意

第一个例子解释的是问题陈述。

在第三个示例中,对于 $$$a = [3, 4, 5, 2, 1, 4, 3, 2]$$$,可能的排列 $$$p$$$ 是 $$$[7, 1, 5, 4, 3, 2, 6]$$$。在这种情况下,Neko 将构造以下数组:

- $$$b = [3, 4, 2, 1, 1, 3, 2]$$$
- $$$c = [4, 5, 5, 2, 4, 4, 3]$$$
- $$$b' = [2, 3, 1, 1, 2, 4, 3]$$$
- $$$c' = [3, 4, 4, 2, 5, 5, 4]$$$