問題一覧 > 通常問題

No.1436 Rgaph

レベル : / AI推定難易度 : 2375 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 16
作問者 : tyawanmusi / テスター : nok0
お気に入りにしたユーザー ProblemId : 5428 / 自分の提出
問題文最終更新日: 2021-03-20 18:42:56
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 287 (順位表) の他の問題:

Problem Statement

There are $N$ cities and $M$ railways. The cities are numbered $1,2,\dots,N$, and the railways are numbered $1,2,\dots,M$. Railway $i$ operates one-way from city $A_i$ to city $B_i$. Each railway is painted either red or green.

Takahashi and Chawanmushi play a game. The rules of the game are as follows.

  • Chawanmushi chooses a pair of integers $(u,v)$ with $1 \le u,v \le N$.
  • Takahashi is placed in city $u$. He repeats, $0$ or more times, riding a railway to move to another city.
  • If it is possible to satisfy all of the following conditions simultaneously, Takahashi wins; otherwise, Chawanmushi wins.
    • Takahashi is in city $v$.
    • Letting $R$ be the number of times he rode a railway painted red and $G$ be the number of times he rode a railway painted green, $R=G$.

You can freely decide the color of each railway. Find $1$ way of painting the railways such that Takahashi is guaranteed to win when both Takahashi and Chawanmushi act optimally. If no such way exists, report that.

Constraints

  • All inputs are integers.
  • $2 \le N \le 1000$
  • $1 \le M \le 2000$
  • $1 \le A_i,B_i \le N$
  • $A_i \neq B_i$
  • The pairs $(A_i,B_i)$ are all distinct.

Input

$N\ M$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_M\ B_M$

Output

$S$

Print a string $S$ of length $M$ on $1$ line. The $i$-th character of $S$ should be R if railway $i$ is painted red, and G if it is painted green. If there are multiple answers, print any one of them.

If no answer exists, print -1 on $1$ line.

Print a newline at the end.

Sample

Sample 1
Input
4 6
1 2
2 3
3 4
4 1
1 3
2 4
Output
RGRGRG

By painting railways $1,3,5$ red and railways $2,4,6$ green, Takahashi is guaranteed to win.

When $(u,v)=(2,4)$, Takahashi moves through the cities in the order $2→3→4$, which gives $R=G$.

When $(u,v)=(1,2)$, he moves through the cities in the order $1→2→4→1→2$. Note that he may ride the same subway $2$ or more times.

When $(u,v)=(4,4)$, he does not move.

Sample 2
Input
4 3
1 2
2 3
3 4
Output
-1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。