AT_dwacon5th_final_a Taro vs. Jiro

给定一个包含 $N$ 个顶点和 $M$ 条无向边的简单连通无向图。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。每个顶点都被涂上了颜色，如果顶点 $i$ 的 $s_i$ 为 `B`，则该顶点为蓝色；如果为 `R`，则为红色。 第 $i$ 条边连接顶点 $a_i$ 和 $b_i$，为双向边。 太郎君和次郎君要用这个图进行游戏。 棋子最初被放在某个顶点上。太郎君和次郎君轮流进行如下操作，太郎君先手： - 操作：从当前棋子所在的顶点选择一个相邻顶点，并将棋子移动到该顶点。 经过 $K$ 次操作后，如果棋子所在的顶点是蓝色，则太郎君获胜，否则次郎君获胜。 棋子初始可以放在 $N$ 个不同的位置。请对于每一种初始位置，判断当两人都采取最优策略时，最终的胜者是谁。

输入以以下格式从标准输入读入。 > $N$ $M$ $K$ > $s$ > $a_1$ $b_1$ > $\vdots$ > $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$ - 给定的图是简单且连通的 ## 样例解释 1  - 棋子会在 $1 \rightarrow 2, 2 \rightarrow 1$ 之间反复移动。 - 如果棋子最初在顶点 $1$，经过 $3$ 次操作后会在顶点 $2$，因此次郎君获胜。 - 如果棋子最初在顶点 $2$，经过 $3$ 次操作后会在顶点 $1$，因此太郎君获胜。 由 ChatGPT 4.1 翻译