分数: 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 。