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

N/A

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