E - Not Dyed by Majority (Cubic Graph) Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

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 個のテストケースが与えられるので，それぞれについて答えてください．

制約

  • T \geq 1
  • N \geq 4
  • 1 つの入力に含まれるテストケースについて，N の総和は 5 \times 10^4 以下である．
  • N は偶数である．
  • 1 \leq A_i < B_i \leq N \ \ \left(1 \leq i \leq \displaystyle\frac{3}{2}N\right)
  • (A_i, B_i) \neq (A_j, B_j) \ \ \left(1 \leq i < j \leq \displaystyle\frac{3}{2}N\right)
  • 与えられるグラフは連結である．
  • 各頂点 k \ (1 \leq k \leq N) は A_i, B_i \ \left(1 \leq i \leq \displaystyle\frac{3}{2}N\right) として合計 3 回現れる．

入力

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

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_{\frac{3}{2}N} B_{\frac{3}{2}N}

出力

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

入力例 1

2
4
1 2
1 3
1 4
2 3
2 4
3 4
10
1 2
1 3
1 4
2 3
2 4
3 5
4 5
5 6
6 7
6 8
7 9
7 10
8 9
8 10
9 10

出力例 1

BWWW
BWWWBWWWBB

1 つ目のテストケースについて考えます． 頂点 1 の色が B となるためには，操作を行う前に頂点 2, 3, 4 のうち 2 つ以上の色が B である必要があります． このとき，頂点 2, 3, 4 のうち少なくとも 1 つに関して，辺で結ばれた頂点のうち 2 つ以上の色が B であるため，操作を行った後の色は B となります． したがって，BWWW という色の列は操作を行った結果としてあり得ません．

Score : 800 points

Problem Statement

You are given a connected simple undirected graph with N vertices and \displaystyle\frac{3}{2}N edges, where N is a positive even number. The vertices are labeled from 1 to N, and the i-th edge connects vertex A_i and vertex B_i. Moreover, for every vertex, the number of incident edges is exactly 3.

You will color each vertex of the given graph either black ( B ) or white ( W ). Here, the string obtained by arranging the colors ( B or W ) of the vertices in the order of vertex labels is called a color sequence.

Determine whether there is a color sequence that cannot result from performing the following operation once when all vertices are colored, and if there is such a color sequence, find one.

Operation: For each vertex k = 1, 2, \dots, N, let C_k be the color that occupies the majority (more than half) of the colors of the vertices connected to k by an edge. For every vertex k, change its color to C_k simultaneously.

There are T test cases to solve.

Constraints

  • T \geq 1
  • N \geq 4
  • The sum of N over the test cases in each input file is at most 5 \times 10^4.
  • N is an even number.
  • 1 \leq A_i < B_i \leq N \ \ \left(1 \leq i \leq \displaystyle\frac{3}{2}N\right)
  • (A_i, B_i) \neq (A_j, B_j) \ \ \left(1 \leq i < j \leq \displaystyle\frac{3}{2}N\right)
  • The given graph is connected.
  • Each vertex k \ (1 \leq k \leq N) appears exactly 3 times as A_i, B_i \ \left(1 \leq i \leq \displaystyle\frac{3}{2}N\right).

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case \mathrm{case}_i \ (1 \leq i \leq T) is in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_{\frac{3}{2}N} B_{\frac{3}{2}N}

Output

Print T lines. For the i-th line, if there is a color sequence that cannot result from performing the operation for the i-th test case, print such a color sequence; otherwise, print -1. If there are multiple color sequences that cannot result from performing the operation, any of them will be considered correct.

Sample Input 1

2
4
1 2
1 3
1 4
2 3
2 4
3 4
10
1 2
1 3
1 4
2 3
2 4
3 5
4 5
5 6
6 7
6 8
7 9
7 10
8 9
8 10
9 10

Sample Output 1

BWWW
BWWWBWWWBB

Let us consider the first test case. For the color of vertex 1 to be B, at least two of the colors of vertices 2, 3, 4 must be B before the operation. Then, for at least one of the vertices 2, 3, 4, at least two of the colors of the vertices connected to that vertex by an edge are B, so the color of that vertex after the operation will be B. Therefore, the color sequence BWWW cannot result from performing the operation.