No.1436 Rgaph
タグ : / 解いたユーザー数 16
作問者 :
nok0
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もしくは右上の雲マークをクリックしてアカウントを作成してください。