Problem Statement

You are given a tree with $N$ vertices. The vertices are labeled from $1$ to $N$, and the $i$-th edge connects vertex $A_i$ and vertex $B_i$. Moreover, for every vertex, the number of incident edges is odd.

You will color each vertex of the given tree either black ( B ) or white ( W ). Here, the string obtained by arranging the colors ( B or W ) of the vertices in the order of vertex labels is called a color sequence.

You are given a color sequence $S$. Determine whether the color sequence $S$ can result from performing the following operation once when all vertices are colored, and if it can, find one possible color sequence before the operation.

Operation: For each vertex $k = 1, 2, \dots, N$, let $C_k$ be the color that occupies the majority (more than half) of the colors of the vertices connected to $k$ by an edge. For every vertex $k$, change its color to $C_k$ simultaneously.

There are $T$ test cases to solve.

Constraints

• $T \geq 1$
• $N \geq 2$
• The sum of $N$ over the test cases in each input file is at most $2 \times 10^5$.
• $1 \leq A_i < B_i \leq N \ \ (1 \leq i \leq N - 1)$
• The given edges $(A_i, B_i) \ (1 \leq i \leq N - 1)$ form a tree.
• Each vertex $k \ (1 \leq k \leq N)$ appears an odd number of times in total as $A_i, B_i \ (1 \leq i \leq N - 1)$.
• $S$ is a string of length $N$ consisting of B and W.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case $\mathrm{case}_i \ (1 \leq i \leq T)$ is in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
S

Output

Print $T$ lines. For the $i$-th line, if the color sequence $S$ can result from performing the operation in the $i$-th test case, print one possible color sequence before the operation; otherwise, print -1. If there are multiple possible color sequences before the operation, any of them will be considered correct.