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

给定一个正的偶数 $N$，有一个包含 $N$ 个顶点、$\displaystyle\frac{3}{2}N$ 条边的连通简单无向图。顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。此外，每个顶点恰好有 $3$ 条边相连。

现在要将图中每个顶点染成黑色（B）或白色（W）。此时，将所有顶点的颜色（B 或 W）按照顶点编号顺序排列，得到的字符串称为颜色序列。

请判断，是否存在某种颜色序列，在对所有顶点进行如下操作一次后不可能出现。如果存在，请给出任意一个这样的颜色序列。

操作： 对于每个顶点 $k=1,2,\dots,N$，令 $C_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_{\frac{3}{2}N}\ B_{\frac{3}{2}N}$

输出 $T$ 行。第 $i$ 行输出第 $i$ 个测试数据的答案。如果存在操作后不可能出现的颜色序列，输出任意一个这样的颜色序列；如果不存在，输出 -1。若有多个满足条件的颜色序列，输出任意一个即可。

限制条件

• $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)$ 在 $A_i,B_i\ \left(1\leq i\leq \displaystyle\frac{3}{2}N\right)$ 中恰好出现 $3$ 次

样例解释 1

以第一个测试数据为例。要使顶点 $1$ 的颜色为 B，则操作前顶点 $2,3,4$ 中至少有 $2$ 个为 B。此时，$2,3,4$ 中至少有 $1$ 个，其相连的顶点中有至少 $2$ 个为 B$，因此操作后颜色为 B。所以，BWWW` 这个颜色序列在操作后是不可能出现的。

由 ChatGPT 4.1 翻译