問題一覧 > 通常問題

No.1436 Rgaph

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 14
作問者 : tyawanmusityawanmusi / テスター : nok0nok0
3 ProblemId : 5428 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-03-20 18:42:56

問題文

$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)$ のときは、移動しません。

サンプル2
入力
4 3
1 2
2 3
3 4
出力
-1

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