No.3056 Disconnected Coloring
Problem Statement
There is a simple connected undirected graph with $N$ vertices and $M$ edges. The $i$-th edge connects vertices $u_i$ and $v_i$ bidirectionally.
You will now paint each edge red or blue.
Determine whether there exists a coloring that satisfies all of the following conditions, and if one exists, output one such coloring.
- Each of the $M$ edges is painted red or blue
- The number of edges painted red and the number of edges painted blue are equal
- It is impossible to reach vertex $N$ from vertex $1$ by traversing only edges painted red
- It is impossible to reach vertex $N$ from vertex $1$ by traversing only edges painted blue
Input
$N\ M$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_M\ v_M$
- $2 \le N \le 2 \times 10^5$
- $1 \le M \le 2 \times 10^5$
- $1 \le u_i < v_i \le N$
- If $i \neq j$, then $(u_i, v_i) \neq (u_j, v_j)$
- The given graph is connected
- All input values are integers
Output
If no coloring satisfying the conditions exists, output -1.
If one exists, output an example of such a coloring as a string of length $M$ consisting of R or B.
Here, if the $i$-th character is R, it means the $i$-th edge is painted red, and if it is B, it means that edge is painted blue.
Print a newline at the end.
Sample
Sample 1
Input
5 4 1 2 2 3 3 4 4 5
Output
BBRR
Sample 2
Input
6 5 1 2 2 3 3 4 4 5 5 6
Output
-1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
tute7627
SPD_9X2