题目描述

小 L 给了你一棵树，树上有 $n-1$ 条边，第 $i$ 条边是 $(u_i,v_i)$，有的边已经确定了方向，小 L 希望你帮忙给剩下每条边确定方向，满足如下条件：

• 对于每个节点 $i$，设 $k_i$ 为 $i$ 节点的入边个数，那么 $W_{i,k_i}=1$，其中 $W_{i,j}$ 是一个输入的 $\in\{0,1\}$ 的数组。
• 设 $01$ 序列 $s_i$ 表示，若第 $i$ 条边从 $u_i$ 指向 $v_i$ ，那么 $s_i=0$，否则 $s_i=1$，在此基础上请你输出字典序最小的一组 $s_i$。

如果不存在，请输出 $-1$，否则输出一行表示字典序最小的 $s_i$。

输入格式

第一行一个整数 $T$ 代表数据组数。

对于每组数据，第一行一个整数 $n$。

接下来 $n-1$ 行，每行两个整数 $u_i,v_i$。

接下来 $n$ 行，每行一个长度为 $d_i+1$ 的 $01$ 串，代表 $W_{i,0}\to W_{i,d_i}$，其中 $d_i$ 是 $i$ 的度数。

接下来一行长度为 $n-1$ 的包含 $01?$ 的字符串，其中 $0,1$ 代表这条边已经定向，$?$ 代表没有定向。

输出格式

如果无解，输出 -1。

否则输出一行长度为 $n-1$ 的 $01$ 字符串代表 $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

提示

对于 $20\%$ 的数据，$T\leq 20,n\leq 16$。

对于 $40\%$ 的数据，$\sum n\leq 100$。

对于 $60\%$ 的数据，$\sum n\leq 2000$。

对于另外 $20$ 的数据，输入的字符串只有 $?$。

对于 $100\%$ 的数据，$2\leq \sum n\leq 5\times 10^5，n\geq 2$。