Problem Description

Little L gave you a tree with $n-1$ edges. The $i$-th edge is $(u_i, v_i)$. Some edges already have fixed directions. Little L wants you to determine the direction of every remaining edge so that the following conditions are satisfied:

• For each node $i$, let $k_i$ be the number of incoming edges of node $i$. Then $W_{i,k_i}=1$, where $W_{i,j}$ is an input array with values in $\{0,1\}$.
• Let the $01$ sequence $s_i$ be defined as follows: if the $i$-th edge is directed from $u_i$ to $v_i$, then $s_i=0$; otherwise $s_i=1$. Based on this, output the lexicographically smallest sequence $s_i$.

If no solution exists, output $-1$. Otherwise, output one line representing the lexicographically smallest $s_i$.

Input Format

The first line contains an integer $T$, the number of test cases.

For each test case, the first line contains an integer $n$.

Then follow $n-1$ lines, each containing two integers $u_i, v_i$.

Then follow $n$ lines, each being a $01$ string of length $d_i+1$, representing $W_{i,0}\to W_{i,d_i}$, where $d_i$ is the degree of node $i$.

Then follows one string of length $n-1$ consisting of 0, 1, and ?. Here 0 and 1 mean the corresponding edge direction is already fixed, and ? means it is not fixed.

Output Format

If there is no solution, output -1.

Otherwise, output one line: a $01$ string of length $n-1$ representing $s$.

3
4
2 1
4 2
1 3
010
100
11
10
???
5
5 3
1 5
4 3
2 1
010
10
010
10
001
?0?0
3
3 1
3 2
01
10
010
??

-1
1000
01

Hint

For $20\%$ of the testdata, $T\leq 20$ and $n\leq 16$.

For $40\%$ of the testdata, $\sum n\leq 100$.

For $60\%$ of the testdata, $\sum n\leq 2000$.

For the other $20\%$ of the testdata, the input string contains only ?.

For $100\%$ of the testdata, $2\leq \sum n\leq 5\times 10^5$ and $n\geq 2$.

Translated by ChatGPT 5