AT_arc161_c [ARC161C] Dyed by Majority (Odd Tree)

[problemUrl]: https://atcoder.jp/contests/arc161/tasks/arc161_c $ 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` を出力せよ． 操作を行う前の色の列として適切なものが複数存在する場合，そのような色の列のうちどれを出力しても正答と見なされる．

### 制約 - $ T\ \geq\ 1 $ - $ N\ \geq\ 2 $ - $ 1 $ つの入力に含まれるテストケースについて，$ N $ の総和は $ 2\ \times\ 10^5 $ 以下である． - $ 1\ \leq\ A_i\