问题描述

给定一个包含 $N$ 个顶点和 $M$ 条无向边的简单连通无向图。每个顶点从 $1$ 到 $N$ 编号，每条边从 $1$ 到 $M$ 编号。每个顶点都有一种颜色，如果顶点 $i$ 的颜色是 B，则为蓝色；如果顶点 $i$ 的颜色是 R，则为红色。

边 $i$ 是连接顶点 $a_i$ 和 $b_i$ 的双向边。

太郎君和次郎君决定使用这个图进行游戏。

一个棋子放在图上的某个顶点上。太郎君和次郎君交替执行以下操作，太郎君先行动。

• 操作：选择放有棋子的顶点的相邻顶点中的一个，将棋子移动到所选的顶点上。

在执行了 $K$ 次操作后，如果棋子所在的顶点的颜色是蓝色，则太郎君获胜；否则次郎君获胜。

初始时棋子可以放在 $N$ 个位置中的任意一个位置。对于每种情况，请确定两个人在最优策略下的赢家。

约束条件

• $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