AT_arc161_c [ARC161C] Dyed by Majority (Odd Tree)

给定一棵有 $N$ 个顶点的树。顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。此外，对于所有顶点，**连接的边的数量都是奇数**。 你需要用黑色（`B`）或白色（`W`）给每个顶点染色。此时，将“每个顶点的颜色（`B` 或 `W`）按顶点编号顺序排列得到的字符串”称为**颜色序列**。 给定一个颜色序列 $S$。请判断是否存在一种顶点染色方式，使得对所有顶点执行以下操作一次后，颜色序列变为 $S$。如果存在，请给出操作前的一种可能的颜色序列；如果不存在，输出 `-1`。 **操作：** 对每个顶点 $k=1,2,\dots,N$，令 $C_k$ 为与其通过边相连的顶点中占多数的颜色。然后，所有顶点同时将自己的颜色变为 $C_k$。 有 $T$ 组测试数据，请分别回答。

输入按以下格式从标准输入给出。 > $T$ > $\mathrm{case}_1$ > $\mathrm{case}_2$ > $\vdots$ > $\mathrm{case}_T$ 每组测试数据 $\mathrm{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$ 行输出第 $i$ 个测试数据的答案。如果存在一种操作前的颜色序列，使得操作后颜色序列为 $S$，则输出其中任意一种；如果不存在，输出 `-1`。

### 限制 - $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$ 中出现的次数**总是奇数** - $S$ 是由 `B` 和 `W` 组成的长度为 $N$ 的字符串 ### 样例解释 1 对于第 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`，输出这些任意一个都视为正确答案。 对于第 2 个测试数据，输入的树中不可能通过一次操作得到颜色序列 `BBWW`。 由 ChatGPT 4.1 翻译