AT_arc143_e [ARC143E] Reversi

有一棵包含 $N$ 个顶点的树。每个顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。此外，每个顶点上都放置有一个“黑白棋”的棋子。每个顶点上的棋子的状态由字符串 $S$ 给出，$S$ 的第 $i$ 个字符为 `B` 时，表示顶点 $i$ 上的棋子正面为黑色；为 `W` 时，表示正面为白色。 请判断是否可以通过以下操作恰好 $N$ 次，将所有顶点上的棋子全部移除。如果可以，请在所有可能的选择顶点顺序 $P_1,P_2,\ldots,P_N$ 中，输出字典序最小的一个。 - 每次操作可以选择一个正面为白色的棋子所在的顶点，将该顶点上的棋子移除。然后，将与该顶点相邻的所有顶点上的棋子翻面。 关于“黑白棋”的棋子：棋子一面为黑色，一面为白色，翻面后正反面颜色互换。 关于数列的字典序：给定两个不同的数列 $S$ 和 $T$，判断大小的算法如下： 记 $S$ 的第 $i$ 个元素为 $S_i$。若 $S$ 字典序小于 $T$，记作 $S < T$，大于则记作 $S > T$。 1. 取 $S$ 和 $T$ 中较短的长度为 $L$，依次比较 $i=1,2,\dots,L$ 时 $S_i$ 与 $T_i$ 是否相等。 2. 若存在 $S_i \neq T_i$，取最小的此类 $i$ 为 $j$，比较 $S_j$ 与 $T_j$，若 $S_j < T_j$，则 $S < T$，否则 $S > T$，算法结束。 3. 若所有 $i$ 都有 $S_i = T_i$，则比较长度，短的字典序更小。

输入以如下格式从标准输入读入： > $N$ > $A_1$ $B_1$ > $\vdots$ > $A_{N-1}$ $B_{N-1}$ > $S$

若目标无法达成，输出 `-1`。若可以达成，输出一行： > $P_1$ $P_2$ $\cdots$ $P_N$

### 数据范围 - $1 \leq N \leq 2 \times 10^5$ - $1 \leq A_i, B_i \leq N$ - 给定的图为一棵树。 - $S$ 是仅由 `B` 和 `W` 组成的长度为 $N$ 的字符串。 ### 样例解释 2 在这种情况下，无法进行任何一次操作。 由 ChatGPT 4.1 翻译