AT_dwacon5th_final_a Taro vs. Jiro

[problemUrl]: https://atcoder.jp/contests/dwacon5th-final/tasks/dwacon5th_final_a $ N $ 頂点 $ M $ 本の無向辺からなる単純連結無向グラフが与えられます。 頂点に $ 1 $ から $ N $ の番号が、辺には $ 1 $ から $ M $ の番号がついています。 それぞれの頂点には色が塗られており、頂点 $ i $ は $ s_i $ が `B` ならば青で、`R` ならば赤で塗られています。 辺 $ i $ は頂点 $ a_i $ と $ b_i $ を双方向につなぐ辺です。 太郎君と次郎君がこのグラフを使ってゲームをすることにしました。 グラフ上のどこかの頂点に $ 1 $ つの駒が置かれています。 太郎君と次郎君は以下の操作を交互に行います。太郎君が最初に操作を行います。 - 操作：駒が置かれている頂点に隣接する頂点を $ 1 $ つ選び、選んだ頂点に駒を移動させる 操作を $ K $ 回行ったのち、駒が置かれている頂点の色が青ならば太郎君の、そうでなければ次郎君の勝利です。 はじめに駒が置かれている位置は $ N $ 通りありえます。 それぞれの場合について、$ 2 $ 人が最適に行動したときの勝者がどちらかを判定してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ s $ $ a_1 $ $ b_1 $ $ : $ $ a_M $ $ b_M $

答えを $ N $ 行に出力せよ。 $ i $ 行目でははじめに頂点 $ i $ に駒が置かれていたときの勝者が太郎君ならば `First`、次郎君ならば `Second` を出力せよ。

### 制約 - $ 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 $ - 与えられるグラフは単純かつ連結 ### Sample Explanation 1 !\[sample input 1\](https://img.atcoder.jp/dwacon5th-final/game\_on\_graph\_sample.png) - 駒は $ 1\ \rightarrow\ 2,\ 2\ \rightarrow\ 1 $ のいずれかの移動を繰り返します。 - 駒が頂点 $ 1 $ に置かれていたならば $ 3 $ 回の操作後には頂点 $ 2 $ に置かれているため次郎君が勝者となります。 - 駒が頂点 $ 2 $ に置かれていたならば $ 3 $ 回の操作後には頂点 $ 1 $ に置かれているため太郎君が勝者となります。