AT_arc161_e [ARC161E] Not Dyed by Majority (Cubic Graph)

[problemUrl]: https://atcoder.jp/contests/arc161/tasks/arc161_e $ N $ を正の**偶数**として，$ N $ 頂点 $ \displaystyle\frac{3}{2}N $ 辺の連結な単純無向グラフが与えられます． 頂点には $ 1 $ から $ N $ までの番号が付いており，$ i $ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結んでいます． また，すべての頂点について，**接続する辺の本数はちょうど $ 3 $** です． 与えられたグラフの各頂点を黒 ( `B` ) か白 ( `W` ) のいずれかの色で塗ります． このとき，「各頂点の色（ `B` または `W` ）を頂点の番号順に並べて得られる文字列」を**色の列**と呼びます． すべての頂点に色が塗られた状態で以下の操作を $ 1 $ 回行った結果として**あり得ない**色の列が存在するかどうかを判定し，存在するならそのような色の列を $ 1 $ つ求めてください． **操作:** 各頂点 $ k\ =\ 1,\ 2,\ \dots,\ N $ に対して，辺で結ばれた頂点の色のうち過半数を占めるものを $ C_k $ とする． すべての頂点について同時に，頂点 $ k $ の色を $ C_k $ に塗り替える． $ T $ 個のテストケースが与えられるので，それぞれについて答えてください．

N/A

N/A

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