题目描述

$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$ $\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 を出力せよ． 操作を行う前の色の列として適切なものが複数存在する場合，そのような色の列のうちどれを出力しても正答と見なされる．

题目大意

给定一棵 $n$ 个节点的树，满足每个点的度数为奇数。你需要把每个点染成黑色或者白色，然后所有点同时变成其相邻点颜色的众数，求一个染色方案使得变化后的颜色为给定序列，或者报告无解。

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

WBBW
-1

提示

制約

• $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$ の文字列である．

Sample Explanation 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 となることはあり得ません．