Cracking Tree Codes#2543
Let \textbf{V} = \{1, 2, \ldots, n\} and \textbf{E} = \{\{u, v\} \mid 1 \leq u, v \leq n\}. A tree \textbf{T} = (V, E) is a connected graph that contains exactly n - 1 edges. For example, a tree \textbf{T}_1 is shown in the figure below.
In \textbf{T}_1 we have \textbf{V} = \{1, 2, 3, 4, 5, 6, 7\}, \textbf{E} = \{\{4, 6\}, \{2, 6\}, \{6, 5\}, \{3, 5\}, \{5, 1\}, \{1, 7\}\}. Professor Minton has discovered a way to encode a tree. The code of a tree is a sequence of n - 2 numbers from the set . For example, \textbf{T}_1 can be encoded as the sequence <6, 5, 6, 5, 1>. If some numbers are missing in the sequence, the sequence is considered broken. To indicate a missing number, the character is used. Given a tree and a broken sequence, you need to determine the missing numbers.
The first line contains the number of test cases . The second line contains an integer . The third line describes the tree and contains 2n - 2 numbers separated by spaces. Each pair of numbers describes an edge. The first pair describes the first edge, the second pair the second edge, and so on. The fourth line contains the sequence of n - 2 numbers, where some of the numbers are replaced by the letter to indicate they are missing.
For each test case, output a single line containing the sequence of missing numbers in the order in which they appear in the input sequence.
Example 1