Problem Description

You are given a simple connected undirected graph with $ N $ vertices and $ M $ edges. The vertices are numbered from $ 1 $ to $ N $, and the edges are numbered from $ 1 $ to $ M $. Each vertex is colored either blue or red: vertex $ i $ is blue if $ s_i $ is B, and red if $ s_i $ is R.

Edge $ i $ connects vertices $ a_i $ and $ b_i $ bidirectionally.

Taro and Jiro decided to play a game using this graph.

A piece is placed on one of the vertices on the graph. Taro and Jiro take turns performing the following operation, starting with Taro.

• Operation: Choose one of the vertices adjacent to the vertex where the piece is located and move the piece to that vertex.

After $ K $ operations, the winner is determined by the color of the vertex where the piece is located: if it is blue, Taro wins; otherwise, Jiro wins.

There are $ N $ possible starting positions for the piece. Determine the winner for each case if both players play optimally.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ K $ $ s $ $ a_1 $ $ b_1 $ $ : $ $ a_M $ $ b_M $

Output Format

Output the answer in $ N $ lines. On the $ i $-th line, output First if Taro wins when the piece is initially on vertex $ i $, and Second if Jiro wins.

Sample Input and Output

Sample Input #1

2 1 3
BR
1 2

Sample Output #1

Second
First

Sample Input #2

2 1 1000000000000000000
BR
1 2

Sample Output #2

First
Second

Sample Input #3

5 7 9
BRRBR
3 1
5 2
4 2
2 1
5 4
5 1
3 2

Sample Output #3

Second
First
First
Second
First

Notes/Hints

Constraints

• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq K \leq 10^{18}$
• $ |s| = N $
• $ s_i $ is either B or R
• $1 \leq a_i, b_i \leq N$
• The given graph is simple and connected

Sample Explanation 1

- The piece can repeatedly move between $1 \rightarrow 2$ or $2 \rightarrow 1$.
- If the piece starts at vertex $ 1 $, it will be at vertex $ 2 $ after 3 moves, so Jiro wins.
- If the piece starts at vertex $ 2 $, it will be at vertex $ 1 $ after 3 moves, so Taro wins.

见题面 Input 部分

见题面 Output 部分