AT_arc143_e [ARC143E] Reversi

[problemUrl]: https://atcoder.jp/contests/arc143/tasks/arc143_e $ 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 $ と決定して，アルゴリズムを終了します．

入力は以下の形式で標準入力から与えられる． > $ 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 $ の文字列である． ### Sample Explanation 2 この場合，一度も操作を行うことができません．