問題一覧 > 通常問題

No.3056 Disconnected Coloring

レベル : / AI推定難易度 : 1725 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 61
作問者 : 👑 tute7627 / テスター : 👑 rin204 SPD_9X2
お気に入りにしたユーザー ProblemId : 11508 / 自分の提出
問題文最終更新日: 2025-03-12 02:53:47
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 460 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。