Description

Little R has a simple undirected graph with $n$ nodes and $m$ edges, in which the nodes are numbered $1 \sim n$. She wants to assign a black or white color to each node in the graph, so that:

• There is at least one black node.
• There is at least one white node.
• For each pair of nodes $(u, v)$, if the color of nodes $u$ and $v$ are different, there are at least two different simple paths from $u$ to $v$.
  • A simple path is a path that does not go through the same node repeatedly on the graph.
  • Two simple paths are considered different, if and only if, either their lengths are different, or there exists at least one positive integer $i$ such that the $i$-th node that the two paths pass through are different.

Alternatively, report that there is no solution.

Input Format

Each test contains multiple testcases.

The first line of the input contains an integer $T$ — the number of test cases. The description of test cases follows.

• The first line of each test case contains two integers $n, m$ — the number of nodes and edges.
• Then, $m$ lines follow, each line contains two integers $u, v$, describing the edges.

It is guaranteed that there are no multiple edges or self-loops in the graph.

Output Format

For each test case:

• If there exists a way to assign the colors, output a string of length $n$ consisting of characters BW only, where the $i$-th node is black if the $i$-th character is B, and white if it is W;
• If there is no solution, output a single line containing an integer $-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

Hint

Subtasks are used in this problem.

• 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): It is guaranteed that the given graph is not connected.
• Subtask 3 (10 pts): It is guaranteed that the degree of each node is $2$.
• Subtask 4 (20 pts): It is guaranteed that $n = m$.
• Subtask 5 (25 pts): No additional constraint.

For all tests, $1 \leq T \leq 10^5$, $2 \leq n \leq 2 \times 10^5$, $0 \leq m \leq 2 \times 10^5$. It is guaranteed that $\sum n \leq 2\times 10^6$, $\sum m \leq 2\times 10^6$, and there are no multiple edges or self-loops in the graph.