多数染色

时间限制：2s
空间限制：1024MB

题目描述

给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$，且每个顶点的度数均为奇数。你要把每个顶点染成黑色 B 或白色 W。随后对所有顶点同时执行一次操作：顶点 $k$ 观察所有相邻顶点的颜色，并把自己的颜色改为其中严格占多数的颜色。由于每个顶点的度数为奇数，多数色总是唯一。

给定操作后的颜色串 $S$。请判断是否存在一种操作前的染色能够得到 $S$；若存在，输出任意一种可行的操作前颜色串，否则输出 -1。每个输入文件包含 $T$ 组测试数据。

输入格式

第一行一个整数 $T$。每组测试数据先给出一个整数 $N$，接下来 $N-1$ 行每行两个整数 $A_i,B_i$ 表示一条边，最后一行给出长度为 $N$ 的颜色串 $S$。

输出格式

对每组测试数据输出一行。若存在可行染色，输出任意一个长度为 $N$、仅含 B 和 W 的操作前颜色串；否则输出 -1。

样例输入 1

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

样例输出 1

WBBW
-1

数据范围

• $T\ge1$，$N\ge2$；
• 每个输入文件中所有测试数据的 $N$ 之和不超过 $2\times10^5$；
• $1\le A_i<B_i\le N$，输入的边构成一棵树；
• 每个顶点的度数均为奇数；
• $S$ 是长度为 $N$、仅含 B 和 W 的字符串。