E - Reversi Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

N 頂点からなる木があります． 各頂点には 1 から N までの番号がついており， i 番目の辺は頂点 A_i と頂点 B_i を結んでいます． また，各頂点にはリバーシの石が 1 つずつ置かれています． 各頂点に置かれている石の状態は文字列 S によって与えられ， S の i 番目の文字が B のとき，頂点 i に置かれている石の表は黒色， S の i 番目の文字が W のとき，頂点 i に置かれている石の表は白色です．

以下の操作を N 回行い，すべての頂点から石を取り除くことが可能かどうか判定してください． また可能ならば，列 P_1,P_2,\ldots,P_N であって，頂点 P_1,P_2,\ldots,P_N をこの順に選ぶことが可能なもののうち，辞書順で最小のものを求めてください．

  • 表が白色の石が置かれている頂点を 1 つ選び，その頂点から石を取り除く． そして，その頂点と隣接する頂点に置かれている石をすべて裏返す．
リバーシの石について リバーシの石は一方の面が黒色，もう一方の面が白色になっており，裏返すと表の色が入れ替わります．
数列の辞書順とは？

相異なる数列 S と数列 T の大小を判定するアルゴリズムを以下に説明します．

以下では S の i 番目の要素を S_i のように表します．また， S が T より辞書順で小さい場合は S \lt T ，大きい場合は S \gt T と表します．

  1. S と T のうち長さが短い方の文字列の長さを L とします．i=1,2,\dots,L に対して S_i と T_i が一致するか調べます．
  2. S_i \neq T_i である i が存在する場合，そのような i のうち最小のものを j とします．そして，S_j と T_j を比較して， S_j が T_j より（数として）小さい場合は S \lt T ，大きい場合は S \gt T と決定して，アルゴリズムを終了します．
  3. S_i \neq T_i である i が存在しない場合， S と T の長さを比較して，S が T より短い場合は S \lt T ，長い場合は S \gt T と決定して，アルゴリズムを終了します．

制約

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq A_i, B_i \leq N
  • 与えられるグラフは木である．
  • S は B と W の文字からなる長さ N の文字列である．

入力

入力は以下の形式で標準入力から与えられる．

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

この場合，一度も操作を行うことができません．

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.
Notes on reversi pieces A reversi piece has a black side and a white side, and flipping it changes which side faces up.
What is the lexicographical order on sequences?

The following is an algorithm to determine the lexicographical order between different sequences S and T.

Below, let S_i denote the i-th element of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.

  1. Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
  2. If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j is less than T_j (as a number), we determine that S \lt T and quit; if S_j is greater than T_j, we determine that S \gt T and quit.
  3. If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.

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

Sample Input 1

4
1 2
2 3
3 4
WBWW

Sample Output 1

1 2 4 3

Sample Input 2

4
1 2
2 3
3 4
BBBB

Sample Output 2

-1

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