Neko and Flashback
题意翻译
### 题意简述
现在有一个长度为 $n$ 的数组 $a$ 和一个长度为 $n−1$ 的排列 $p$。分别构造四个数列 $b$,$c$,$b'$,$c'$,其定义如下:
$$
b_i=min(a_i,a_{i+1})
$$
$$
c_i=max(a_i,a_{i+1})
$$
$$
b_i'=b_{p_i}
$$
$$
c_i'=c_{p_i}
$$
现给定序列 $b'$ 和 $ c'$ ,求出任何一个合法的序列 $a$。
如果没有任何一个可能的序列,那么输出 $-1$。
$2 \le n\le 10^5 , 1\le b_i' , c_i' \le 10^9$。
题目描述
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 $ .
输入输出格式
输入格式
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 $ ).
输出格式
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.
输入输出样例
输入样例 #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
说明
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] $