P11022 「LAOI-6」Yet Another Graph Coloration Problem

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.

**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.

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$.

**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.