← 返回题目列表

AtCoder · arc161_e

E. 未被多数染色(立方图)

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

给你一个连通的简单无向图 N 顶点和 \displaystyle\frac{3}{2}N 边缘,其中 N 是一个积极的 偶数。 顶点标记为 1 to N,以及 i第一条边连接顶点 A_i 和顶点 B_i。 此外,对于每个顶点, 入射边的数量恰好是 3.

您将给定图形的每个顶点着色为黑色 ( B )或白色( W )。 这里,通过排列颜色获得的字符串( B or W )按顶点标签顺序排列的顶点称为 颜色序列.

判断是否存在颜色序列 不能 当所有顶点都着色时执行一次以下操作的结果,如果存在这样的颜色序列,则找到一个。

操作: 对于每个顶点 k = 1, 2, \dots, N,让 C_k 是占据连接到的顶点颜色的大多数(超过一半)的颜色 k 的边缘。 对于每个顶点 k,将其颜色更改为 C_k 同时进行。

有 T 测试用例解决。

约束

  • T \geq 1
  • N \geq 4
  • 总和 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) 出现 正是 3 次 as A_i, B_i \ \left(1 \leq i \leq \displaystyle\frac{3}{2}N\right).

输入

输入由标准输入按以下格式给出:

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 是 B,至少两种顶点颜色 2, 3, 4 必须是 B 操作前。 然后,对于至少一个顶点 2, 3, 4,通过边连接到该顶点的顶点的至少两种颜色是 B,所以操作后该顶点的颜色将为 B。 因此,颜色顺序 执行该操作无法产生 BWWW 。