P14655 同归月

小 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$。

对于 $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$。