配点 : $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$ つ選び，その頂点から石を取り除く． そして，その頂点と隣接する頂点に置かれている石をすべて裏返す．

制約

• $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$

4
1 2
2 3
3 4
WBWW

1 2 4 3

4
1 2
2 3
3 4
BBBB

-1

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