A - Taro vs. Jiro /

Time Limit: 2.525 sec / Memory Limit: 1024 MB

配点 : 500

問題文

N 頂点 M 本の無向辺からなる単純連結無向グラフが与えられます。 頂点に 1 から N の番号が、辺には 1 から M の番号がついています。 それぞれの頂点には色が塗られており、頂点 is_iB ならば青で、R ならば赤で塗られています。

i は頂点 a_ib_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_iB あるいは 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

sample input 1

  • 駒は 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