A - Taro vs. Jiro
Editorial
/
Time Limit: 2.525 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 頂点 M 本の無向辺からなる単純連結無向グラフが与えられます。
頂点に 1 から N の番号が、辺には 1 から M の番号がついています。
それぞれの頂点には色が塗られており、頂点 i は s_i が B
ならば青で、R
ならば赤で塗られています。
辺 i は頂点 a_i と b_i を双方向につなぐ辺です。
太郎君と次郎君がこのグラフを使ってゲームをすることにしました。
グラフ上のどこかの頂点に 1 つの駒が置かれています。 太郎君と次郎君は以下の操作を交互に行います。太郎君が最初に操作を行います。
- 操作:駒が置かれている頂点に隣接する頂点を 1 つ選び、選んだ頂点に駒を移動させる
操作を K 回行ったのち、駒が置かれている頂点の色が青ならば太郎君の、そうでなければ次郎君の勝利です。
はじめに駒が置かれている位置は N 通りありえます。 それぞれの場合について、2 人が最適に行動したときの勝者がどちらかを判定してください。
制約
- 2 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq K \leq 10^{18}
- |s| = N
- s_i は
B
あるいはR
- 1 \leq a_i,b_i \leq N
- 与えられるグラフは単純かつ連結
入力
入力は以下の形式で標準入力から与えられる。
N M K s a_1 b_1 : a_M b_M
出力
答えを N 行に出力せよ。
i 行目でははじめに頂点 i に駒が置かれていたときの勝者が太郎君ならば First
、次郎君ならば Second
を出力せよ。
入力例1
2 1 3 BR 1 2
出力例1
Second First
- 駒は 1 \rightarrow 2, 2 \rightarrow 1 のいずれかの移動を繰り返します。
- 駒が頂点 1 に置かれていたならば 3 回の操作後には頂点 2 に置かれているため次郎君が勝者となります。
- 駒が頂点 2 に置かれていたならば 3 回の操作後には頂点 1 に置かれているため太郎君が勝者となります。
入力例2
2 1 1000000000000000000 BR 1 2
出力例2
First Second
入力例3
5 7 9 BRRBR 3 1 5 2 4 2 2 1 5 4 5 1 3 2
出力例3
Second First First Second First