Score : $700$ points

Problem Statement

We have a tree with $N$ vertices. The vertices are numbered $1$ to $N$, and the $i$-th edge connects Vertex $A_i$ and Vertex $B_i$. Additionally, each vertex has a reversi piece on it. The status of the piece on each vertex is given by a string $S$: if the $i$-th character of $S$ is B, the piece on Vertex $i$ is placed with the black side up; if the $i$-th character of $S$ is W, the piece on Vertex $i$ is placed with the white side up.

Determine whether it is possible to perform the operation below $N$ times to remove the pieces from all vertices. If it is possible, find the lexicographically smallest possible sequence $P_1, P_2, \ldots, P_N$ such that Vertices $P_1, P_2, \ldots, P_N$ can be chosen in this order during the process.

• Choose a vertex containing a piece with the white side up, and remove the piece from that vertex. Then, flip all pieces on the vertices adjacent to that vertex.

Constraints

• $1 \leq N \leq 2\times 10^5$
• $1 \leq A_i, B_i \leq N$
• The given graph is a tree.
• $S$ is a string of length $N$ consisting of the characters B and W.

Input

Input is given from Standard Input in the following format:

$N$

$A_1$ $B_1$

$\vdots$

$A_{N-1}$ $B_{N-1}$

$S$

Output

If the objective is unachievable, print -1. If it is achievable, print the answer in the following format:

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

4
1 2
2 3
3 4
WBWW

1 2 4 3

4
1 2
2 3
3 4
BBBB

-1

In this case, you cannot perform the operation at all.