問題文

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
• 与えられるグラフは単純かつ連結

入力例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