CF1152E Neko and Flashback

长度为 $k$ 的排列是指从 $1$ 到 $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$）。

如果不存在数组 $a$ 和排列 $p$ 能够得到给定的 $b'$ 和 $c'$，输出 $-1$。否则，输出 $n$ 个正整数 $a_i$（$1 \le a_i \le 10^9$），表示数组 $a$ 的元素。 如果有多组解，输出任意一组均可。

第一个样例的解释见题面。 在第三个样例中，对于 $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]$ 由 ChatGPT 4.1 翻译