eolymp
bolt
Try our new interface for solving problems
Problems

Cracking Tree Codes

Cracking Tree Codes

\includegraphics{https://static.e-olymp.com/content/cc/cc8a15c4c87b4c7e92efe076a394dd47b084fd99.jpg} Let \textbf{V = \{1, 2, …, n\}} and \textbf{E \{\{u, v\} | 1 }≤\textbf{ u, v }≤\textbf{ n\}}. A tree \textbf{T = (V,E)} is a graph that is connected and has exactly \textbf{n-1} edges. For example, a tree \textbf{T_1} is shown in the figure below. \includegraphics{https://static.e-olymp.com/content/9d/9d2372ca789360204366e77fdb1b55bbb4b0f361.jpg} In \textbf{T_1} we have \textbf{V = \{1,2,3,4,5,6,7\}} and \textbf{E = \{\{4, 6\}, \{2, 6\}, \{6, 5\}, \{3, 5\}, \{5, 1\}, \{1, 7\}\}}. Professor Minton has found a way to encrypt a tree. An encrypted tree is a sequence of \textbf{n-2} numbers from \textbf{V}. For instance, \textbf{T_1} would have sequence \textbf{<6, 5, 6, 5, 1>}. A sequence is broken if some numbers are missing. We use the alphabet \textbf{x} to represent a missing number in the sequence. Given a tree and a broken sequence, write a program to find the missing numbers. \InputFile The first line is the number \textbf{t} of test cases. The second line is \textbf{n}. The third line is the description of a tree in the form of \textbf{2n-2} numbers separated by a blank. The first pair of numbers represents the first edge; the second pair represents the second edge; and so on. The fourth line contains a broken sequence in the form of \textbf{n-2} numbers, each separated by a blank, where some of these numbers are marked with \textbf{x}ʹs to indicate missing. \OutputFile The output contains \textbf{t} lines. The first line contains missing numbers of the first test case in the same order as the inputʹs. The second line contains missing numbers of the second test case in the same order as the inputʹs and so on.
Time limit 1 second
Memory limit 64 MiB
Input example #1
1
7
4 6 2 6 6 5 3 5 5 1 1 7
6 x x 5 1
Output example #1
5 6