配点 : $500$ 点

問題文

$N$ 頂点の木が与えられます． 頂点には $1$ から $N$ までの番号が付いており，$i$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を結んでいます． また，すべての頂点について，接続する辺の本数は奇数です．

与えられた木の各頂点を黒 ( B ) か白 ( W ) のいずれかの色で塗ります． このとき，「各頂点の色（ B または W ）を頂点の番号順に並べて得られる文字列」を色の列と呼びます．

色の列 $S$ が与えられます． すべての頂点に色が塗られた状態で以下の操作を $1$ 回行った結果，色の列が $S$ となることがあり得るかどうかを判定し，あり得るなら操作を行う前の色の列として適切なものを $1$ つ求めてください．

操作: 各頂点 $k = 1, 2, \dots, N$ に対して，辺で結ばれた頂点の色のうち過半数を占めるものを $C_k$ とする． すべての頂点について同時に，頂点 $k$ の色を $C_k$ に塗り替える．

$T$ 個のテストケースが与えられるので，それぞれについて答えてください．

制約

• $T \geq 1$
• $N \geq 2$
• $1$ つの入力に含まれるテストケースについて，$N$ の総和は $2 \times 10^5$ 以下である．
• $1 \leq A_i < B_i \leq N \ \ (1 \leq i \leq N - 1)$
• 与えられる辺 $(A_i, B_i) \ (1 \leq i \leq N - 1)$ は木をなす．
• 各頂点 $k \ (1 \leq k \leq N)$ は $A_i, B_i \ (1 \leq i \leq N - 1)$ として合計奇数回現れる．
• $S$ は B, W からなる長さ $N$ の文字列である．

入力

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

$T$

$\mathrm{case}_1$

$\mathrm{case}_2$

$\vdots$

$\mathrm{case}_T$

各テストケース $\mathrm{case}_i \ (1 \leq i \leq T)$ は以下の形式である．

$N$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

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

$S$

出力

$T$ 行出力せよ． $i$ 行目には，$i$ 番目のテストケースについて，操作の結果として色の列が $S$ となることがあり得るなら操作を行う前の色の列として適切なものを，あり得ないなら -1 を出力せよ． 操作を行う前の色の列として適切なものが複数存在する場合，そのような色の列のうちどれを出力しても正答と見なされる．

2
4
1 2
1 3
1 4
BWWW
4
1 2
1 3
1 4
BBWW

WBBW
-1

$1$ つ目のテストケースについて，操作を行う前の色の列が WBBW であったとします． このとき，

• 頂点 $1$ について，辺で結ばれた頂点 $2, 3, 4$ の色はそれぞれ B, B, W であり，過半数を占めるのは $C_1 = {}$B，
• 頂点 $2$ について，辺で結ばれた頂点 $1$ の色は W であり，過半数を占めるのは $C_2 = {}$W，
• 頂点 $3$ について，辺で結ばれた頂点 $1$ の色は W であり，過半数を占めるのは $C_3 = {}$W，
• 頂点 $4$ について，辺で結ばれた頂点 $1$ の色は W であり，過半数を占めるのは $C_4 = {}$W となります．

したがって，操作後の色の列は BWWW となり，条件を満たします． 同様に，操作前の色の列が WBBB, WBWB, WWBB であった場合にも，操作後の色の列は BWWW となり，これらのうちどれを出力しても正答と見なされます。

$2$ つ目のテストケースについて，入力された木において操作を行った結果，色の列が BBWW となることはあり得ません．