Cracking Tree Codes

Let $V = \{1, 2, \dots, n\}$ and $E \subset \{\{u, v\} \mid 1 \le u, v \le n\}$. A tree $T = (V, E)$ is a graph that is connected and has exactly $n - 1$ edges. The figure below shows a tree $T_1$.

In $T_1$ we have $V = \{1, 2, 3, 4, 5, 6, 7\}$ and $E = \{\{4, 6\}, \{2, 6\}, \{6, 5\}, \{3, 5\}, \{5, 1\}, \{1, 7\}\}$.

Professor Minton found a way to encrypt a tree. The code of a tree is a sequence of $n - 2$ numbers from $V$, built by repeating these three steps $n - 2$ times.

1. In the part of the tree that is left, take the leaf (a vertex of degree $1$) with the smallest number.
2. Append the number of the only vertex adjacent to that leaf to the sequence.
3. Delete that leaf from the tree.

After $n - 2$ rounds two vertices remain. The code of $T_1$ is $\langle 6, 5, 6, 5, 1 \rangle$.

A code sometimes arrives with a few of its numbers erased. Every erased position is written as the letter x. Given a tree and a code with erased numbers, write a program that recovers the erased numbers.

The first line contains the number of test cases $t$. ($1 \le t \le 10$)

Each test case takes three lines. The first line contains the number of vertices $n$. ($2 \le n \le 10000$) The second line contains $2n - 2$ numbers separated by blanks that describe the tree. Reading two numbers at a time, the first pair is the first edge, the second pair is the second edge, and so on. The third line contains the code with erased numbers as $n - 2$ tokens. Each token is either a vertex number or the letter x for an erased position. When $n = 2$ the third line is empty.

The numbers that were not erased agree with the code of the given tree. The sum of $n$ over all test cases is at most $30000$.

For each test case print one line holding the erased numbers in the order they appear in the input, separated by single blanks. If nothing was erased, print an empty line.