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

题意翻译

### 题意简述 现在有一个长度为 $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$。