题目描述

给定一个包含 $N$ 个顶点的树。顶点从 $1$ 到 $N$ 编号，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。此外，每个顶点上都有一个黑白棋子。每个顶点上的棋子状态由字符串 $S$ 给出：如果 $S$ 的第 $i$ 个字符是 B，则表示顶点 $i$ 上的棋子是黑色朝上；如果 $S$ 的第 $i$ 个字符是 W，则表示顶点 $i$ 上的棋子是白色朝上。

判断是否可以通过最多执行 $N$ 次以下操作来移除所有顶点上的棋子。如果可以，则找到字典序最小的可能序列 $P_1, P_2, \\ldots, P_N$，使得在整个过程中可以按照 $P_1, P_2, \\ldots, P_N$ 的顺序选择相应的顶点。

• 选择一个顶点，其上的棋子是白色朝上，并将该顶点上的棋子移除。然后翻转与该顶点相邻的所有顶点上的棋子。

关于黑白棋子的说明，黑白棋子具有黑面和白面，翻转棋子将改变朝上的一面。关于序列的字典序排序规则如下：

以下是确定不同序列 $S$ 和 $T$ 字典序的算法。

设 $S_i$ 表示 $S$ 的第 $i$ 个元素。此外，如果 $S$ 的字典序小于 $T$，我们将表示为 $S \\lt T$；如果 $S$ 的字典序大于 $T$，我们将表示为 $S \\gt T$。

1. 让 $L$ 成为 $S$ 和 $T$ 的长度中较小的值。对于每个 $i=1,2,\\dots,L$，我们检查 $S_i$ 和 $T_i$ 是否相同。
2. 如果存在 $i$ 使得 $S_i \\neq T_i$，那么让 $j$ 成为最小的这样的 $i$。然后我们比较 $S_j$ 和 $T_j$。如果 $S_j$ 小于 $T_j$（作为一个数字），我们判断 $S \\lt T$ 并退出；如果 $S_j$ 大于 $T_j$，我们判断 $S \\gt T$ 并退出。
3. 如果不存在 $i$ 使得 $S_i \\neq T_i$，我们比较 $S$ 和 $T$ 的长度。如果 $S$ 的长度小于 $T$，我们判断 $S \\lt T$ 并退出；如果 $S$ 的长度大于 $T$，我们判断 $S \\gt T$ 并退出。

约束条件

• $1 \\leq N \\leq 2\\times 10^5$
• $1 \\leq A_i, B_i \\leq N$
• 给定的图是一棵树。
• $S$ 是长度为 $N$ 的字符串，由字符 B 和 W 组成。

输入

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

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

输出

如果目标是无法达成的，输出 -1。如果可以达成，则按照以下格式输出答案：

$P_1$ $P_2$ $\\cdots$ $P_N$

示例 1

4
1 2
2 3
3 4
WBWW

示例 1 输出

1 2 4 3 

示例 2

4
1 2
2 3
3 4
BBBB

示例 2 输出

-1

在这种情况下，无法进行任何操作。