問題文

$N$ 個の都市と $M$ 個の鉄道があります。各都市には $1,2,\dots,N$ の番号がつけられ、各鉄道にも $1,2,\dots,M$ の番号がつけられています。鉄道 $i$ は都市 $A_i$ から都市 $B_i$ までの 一方通行 運行をしています。各鉄道は 赤色 か 緑色 に塗られています。

高橋くんと茶碗蒸しくんはゲームをします。ゲームのルールは以下の通りです。

• 茶碗蒸しくんは、 $1 \le u,v \le N$ である整数の組 $(u,v)$ を選ぶ。
• 高橋くんは都市 $u$ に置かれる。$0$ 回以上、鉄道に乗り他の都市へ移動することを繰り返す。
• 以下の条件を同時に満たすことが可能ならば高橋くんの勝利、不可能ならば茶碗蒸しくんの勝利。
• 高橋くんが都市 $v$ にいる。
• 赤色 に塗られた鉄道に乗った回数を $R$ 、 緑色 に塗られた鉄道に乗った回数を $G$ とし、$R=G$

あなたはそれぞれの鉄道の色を自由に決めることができます。高橋くんと茶碗蒸しくんが最適に行動したとき、高橋くんが必勝となるような色の塗り方を $1$ つ求めてください。存在しない場合はそのことを報告してください。

制約

• 入力はすべて整数
• $2 \le N \le 1000$
• $1 \le M \le 2000$
• $1 \le A_i,B_i \le N$
• $A_i \neq B_i$
• 組 $(A_i,B_i)$ はすべて異なる

入力

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

出力

$S$

長さ $M$ の文字列 $S$ を $1$ 行に出力してください。鉄道 $i$ を 赤色 に塗るときは $S$ の $i$ 文字目をRに、 緑色 に塗るときはGにしてください。答えが複数存在する場合はその一例を出力してください。

答えが存在しない場合は、-1を $1$ 行に出力してください。

最後に改行してください。

サンプル

サンプル1

入力

4 6
1 2
2 3
3 4
4 1
1 3
2 4

出力

RGRGRG

鉄道 $1,3,5$ を 赤色 に、鉄道 $2,4,6$ を 緑色 に塗ることで、高橋くんが必勝となります。

$(u,v)=(2,4)$ のときは、高橋くんは都市を $2→3→4$ の順に移動することで $R=G$ となります。

$(u,v)=(1,2)$ のときは、都市を $1→2→4→1→2$ の順に移動します。同じ地下鉄に $2$ 回以上乗ってもよいことに注意してください。

$(u,v)=(4,4)$ のときは、移動しません。

4 3
1 2
2 3
3 4

-1