题目背景

English statement. You must submit your code at the Chinese version of the statement.

题目描述

小 R 有一张 $n$ 个节点和 $m$ 条的边简单无向图，节点的编号依次为 $1 \sim n$。她想要为图中的每个节点分配黑色或白色的颜色，使得：

• 有至少 $1$ 个黑色节点；
• 有至少 $1$ 个白色节点；
• 对于任何一对点对 $(u, v)$，只要 $u$ 和 $v$ 的颜色不同，就存在至少 $2$ 条从 $u$ 到 $v$ 的不同的简单路径。
  • 简单路径是图上指不重复经过同一点的路径。
  • 若两条简单路径不同，要么其长度不同，要么至少存在一个正整数 $i$ 使两条路径经过的第 $i$ 个点不同。

或者，报告解不存在。

输入格式

本题有多组数据。

第一行，一个整数 $T$，表示数据组数。对于每组数据：

• 第一行，两个整数 $n, m$，表示图的节点数和边数。
• 接下来 $m$ 行，每行两个整数 $u, v$，表示有一条 $u, v$ 之间的边。

保证给出的图无重边、无自环。

输出格式

对于每组数据：

• 若有解，输出一行长为 $n$ 的字符串，第 $i$ 个字符为 B 表示 $i$ 号节点为黑色，为 W 表示 $i$ 号节点为白色；
• 若无解，仅输出一行一个整数 $-1$。

如果有多种合法的解，你只需要输出任意一种即可。

3
4 5
1 2
1 3
1 4
2 3
3 4
5 6
1 2
1 3
1 5
2 3
2 4
3 4
6 10
1 2
1 3
1 5
2 3
2 4
2 5
2 6
3 5
3 6
4 6

BWBW
BBWWB
BWBWBW

1
4 3
1 2
1 3
2 3

-1

提示

本题采用捆绑测试。

• Subtask 0（15 pts）：$\sum 2^n \leq 2^{16}$。
• Subtask 1（25 pts）：$n \leq 3\times 10^3$，$m \leq 3\times 10^3$，$\sum n \leq 10^4$，$\sum m \leq 2\times 10^4$。
• Subtask 2（5 pts）：保证图不连通。
• Subtask 3（10 pts）：保证每个点的度数均为 $2$。
• Subtask 4（20 pts）：保证 $n = m$。
• Subtask 5（25 pts）：无特殊限制。

对于所有数据，保证 $1 \leq T \leq 10^5$，$2 \leq n \leq 2 \times 10^5$，$0 \leq m \leq 2 \times 10^5$，$\sum n \leq 2\times 10^6$，$\sum m \leq 2\times 10^6$，保证给出的图无重边、无自环。