CF1152E.Neko and Flashback

A permutation of length $k$ is a sequence of $k$ integers from $1$ to $k$ containing each integer exactly once. For example, the sequence $[3, 1, 2]$ is a permutation of length $3$.

When Neko was five, he thought of an array $a$ of $n$ positive integers and a permutation $p$ of length $n - 1$. Then, he performed the following:

• Constructed an array $b$ of length $n-1$, where $b_i = \min(a_i, a_{i+1})$.
• Constructed an array $c$ of length $n-1$, where $c_i = \max(a_i, a_{i+1})$.
• Constructed an array $b'$ of length $n-1$, where $b'_i = b_{p_i}$.
• Constructed an array $c'$ of length $n-1$, where $c'_i = c_{p_i}$.

For example, if the array $a$ was $[3, 4, 6, 5, 7]$ and permutation $p$ was $[2, 4, 1, 3]$, then Neko would have constructed the following arrays:

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

Then, he wrote two arrays $b'$ and $c'$ on a piece of paper and forgot about it. 14 years later, when he was cleaning up his room, he discovered this old piece of paper with two arrays $b'$ and $c'$ written on it. However he can't remember the array $a$ and permutation $p$ he used.

In case Neko made a mistake and there is no array $a$ and permutation $p$ resulting in such $b'$ and $c'$, print -1. Otherwise, help him recover any possible array $a$.

长度为 $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$。

The first line contains an integer $n$ ($2 \leq n \leq 10^5$) — the number of elements in array $a$.

The second line contains $n-1$ integers $b'_1, b'_2, \ldots, b'_{n-1}$ ($1 \leq b'_i \leq 10^9$).

The third line contains $n-1$ integers $c'_1, c'_2, \ldots, c'_{n-1}$ ($1 \leq c'_i \leq 10^9$).

第一行包含一个整数 $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$）。

If Neko made a mistake and there is no array $a$ and a permutation $p$ leading to the $b'$ and $c'$, print -1. Otherwise, print $n$ positive integers $a_i$ ($1 \le a_i \le 10^9$), denoting the elements of the array $a$.

If there are multiple possible solutions, print any of them.

如果 Neko 犯了一个错误，使得不存在数组 $a$ 和排列 $p$ 能够生成 $b'$ 和 $c'$，则输出 -1。否则，输出 $n$ 个正整数 $a_i$（$1 \le a_i \le 10^9$），表示数组 $a$ 的元素。

若存在多个可能的解，输出任意一个即可。

The first example is explained is the problem statement.

In the third example, for $a = [3, 4, 5, 2, 1, 4, 3, 2]$, a possible permutation $p$ is $[7, 1, 5, 4, 3, 2, 6]$. In that case, Neko would have constructed the following arrays:

• $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]$

第一个示例在题目描述中已作解释。

在第三个示例中，对于 $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]$