问题描述

给定一个具有 $N$ 个顶点和 $\\displaystyle\\frac{3}{2}N$ 条边的连通简单无向图，其中 $N$ 是正的偶数。顶点从 $1$ 到 $N$ 进行标记，第 $i$ 条边连接着顶点 $A_i$ 和顶点 $B_i$。而且，对于每个顶点，与之关联的边数恰好为 $3$。

你需要为给定的图的每个顶点上色，可以选择黑色（B）或白色（W）。这里，按照顶点标签顺序排列顶点颜色（B 或 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)$ 作为 $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$ 的颜色为 B，在执行操作之前，顶点 $2, 3, 4$ 中至少有两个顶点的颜色是 B。然后，对于顶点 $2, 3, 4$ 中的至少一个顶点，与该顶点相连的顶点的颜色中至少有两个顶点的颜色是 B，所以该顶点在操作后的颜色将为 B。因此，颜色序列 BWWW 不能通过执行操作得到。