问题描述

给定一个包含 $N$ 个顶点的树。顶点从 $1$ 到 $N$ 进行标记，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。而且，对于每个顶点，与其相连的边的数目是奇数。

你需要给给定的树的每个顶点着色，可以选择黑色（B）或白色（W）。这里，按照顶点标签顺序排列各个顶点的颜色（B 或 W）所得到的字符串称为颜色序列。

给定一个颜色序列 $S$，判断是否可以通过执行以下操作一次得到颜色序列 $S$，如果可以，则找到一种可能的操作前的颜色序列。

**操作：**对于每个顶点 $k = 1, 2, \dots, N$，令 $C_k$ 是与顶点 $k$ 相连的顶点中占据多数（超过一半）的颜色。对于每个顶点 $k$，同时将它的颜色改为 $C_k$。

有 $T$ 个测试用例需要解决。

约束条件

• $T \geq 1$
• $N \geq 2$
• 输入文件中所有测试用例中 $N$ 的总和至多为 $2 \times 10^5$。
• $1 \leq A_i < B_i \leq N \ \ (1 \leq i \leq N - 1)$
• 给定的边 $(A_i, B_i) \ (1 \leq i \leq N - 1)$ 构成一棵树。
• 每个顶点 $k \ (1 \leq k \leq N)$ 作为 $A_i, B_i \ (1 \leq i \leq N - 1)$ 出现的总次数是奇数。
• $S$ 是一个由 B 和 W 组成的长度为 $N$ 的字符串。

输入

输入以以下格式从标准输入中给出：

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

每个测试用例 $case_i \ (1 \leq i \leq T)$ 的格式如下：

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

输出

输出 $T$ 行。对于第 $i$ 行，如果颜色序列 $S$ 可以通过第 $i$ 个测试用例中的操作得到，输出一种可能的操作前的颜色序列；否则，输出 -1。如果有多种可能的操作前的颜色序列，则输出其中任意一种即可。

示例输入 1

2
4
1 2
1 3
1 4
BWWW
4
1 2
1 3
1 4
BBWW

示例输出 1

WBBW
-1

对于第一个测试用例，假设操作前的颜色序列为 WBBW。在这种情况下，

• 对于顶点 $1$，与之相连的顶点 $2, 3, 4$ 的颜色分别是 B, B, W，因此 $C_1 = {}$B 占据多数；
• 对于顶点 $2$，与之相连的顶点 $1$ 的颜色是 W，因此 $C_2 = {}$W 占据多数；
• 对于顶点 $3$，与之相连的顶点 $1$ 的颜色是 W，因此 $C_3 = {}$W 占据多数；
• 对于顶点 $4$，与之相连的顶点 $1$ 的颜色是 W，因此 $C_4 = {}$W 占据多数。

因此，操作后的颜色序列是 BWWW，满足条件。同样地，如果操作前的颜色序列是 WBBB、WBWB 或 WWBB，操作后的颜色序列都会是 BWWW，其中任意一种都被认为是正确的。

对于第二个测试用例，颜色序列 BBWW 无法由给定的树进行此操作得到。