Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 個の文字列 S _ 1,S _ 2,\ldots,S _ N が与えられます。 S _ i\ (1\leq i\leq N) は英小文字からなる長さ 10 以下の空でない文字列で、互いに異なります。
先手太郎君と後手次郎君がしりとりをします。 このしりとりでは、先手太郎君と後手次郎君の手番が交互に訪れます。 はじめの手番は先手太郎君の手番です。 それぞれのプレイヤーは自分の手番において整数 i\ (1\leq i\leq N) を 1 つ選びます。 このとき、i は次の 2 つの条件を満たしていなければなりません。
- i は、しりとりが開始してからこれまでの 2 人の手番で選ばれたどの整数とも異なる
- この手番がしりとりの最初の手番であるか、直前に選ばれた整数を j として、S _ j の最後の文字と S _ i の最初の文字が等しい
条件を満たす i を選べなくなったプレイヤーの負けで、負けなかったプレイヤーの勝ちです。
2 人が最適に行動したときに勝つのはどちらかを判定してください。
制約
- 1 \leq N \leq 16
- N は整数
- S _ i\ (1\leq i\leq N) は英小文字からなる長さ 10 以下の空でない文字列
- S _ i\neq S _ j\ (1\leq i\lt j\leq N)
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
2 人が最適に行動したとき、先手太郎君が勝つなら First
、後手次郎君が勝つなら Second
と出力せよ。
入力例 1
6 enum float if modint takahashi template
出力例 1
First
例えば、ゲームは以下のように進行します。 この進行例では 2 人の行動が必ずしも最適とは限らないことに注意してください。
- 先手太郎君が i=3 を選ぶ。S _ i=
if
である。 - 後手次郎君が i=2 を選ぶ。S _ i=
float
であり、if
の最後の文字とfloat
の最初の文字は等しい。 - 先手太郎君が i=5 を選ぶ。S _ i=
takahashi
であり、float
の最後の文字とtakahashi
の最初の文字は等しい。 - 後手次郎君は i\neq2,3,5 であって S _ i の最初の文字が
i
と等しいものを選べないため、負ける。
このとき、先手太郎君が勝ちます。
入力例 2
10 catch chokudai class continue copy exec havoc intrinsic static yucatec
出力例 2
Second
入力例 3
16 mnofcmzsdx lgeowlxuqm ouimgdjxlo jhwttcycwl jbcuioqbsj mdjfikdwix jhvdpuxfil peekycgxco sbvxszools xuuqebcrzp jsciwvdqzl obblxzjhco ptobhnpfpo muizaqtpgx jtgjnbtzcl sivwidaszs
出力例 3
First
Score : 500 points
Problem Statement
You are given N strings S _ 1,S _ 2,\ldots,S _ N. S _ i\ (1\leq i\leq N) is a non-empty string of length at most 10 consisting of lowercase English letters, and the strings are pairwise distinct.
Taro the First and Jiro the Second play a word-chain game. In this game, the two players take alternating turns, with Taro the First going first. In each player's turn, the player chooses an integer i\ (1\leq i\leq N), which should satisfy the following two conditions:
- i is different from any integer chosen by the two players so far since the game started;
- the current turn is the first turn of the game, or the last character of S_j equals the first character of S_i, where j is the last integer chosen.
The player who is unable to choose a conforming i loses; the other player wins.
Determine which player will win if the two players play optimally.
Constraints
- 1 \leq N \leq 16
- N is an integer.
- S _ i\ (1\leq i\leq N) is a non-empty string of length at most 10 consisting of lowercase English letters.
- S _ i\neq S _ j\ (1\leq i\lt j\leq N)
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print First
if Taro the First wins when the two players play optimally; print Second
if Jiro the Second wins.
Sample Input 1
6 enum float if modint takahashi template
Sample Output 1
First
For example, the game progresses as follows. Note that the two players may not be playing optimally in this example.
- Taro the First chooses i=3. S _ i=
if
. - Jiro the Second chooses i=2. S _ i=
float
, and the last character ofif
equals the first character offloat
. - Taro the First chooses i=5. S _ i=
takahashi
, and the last character offloat
equals the first character oftakahashi
. - Jiro the Second is unable to choose i\neq2,3,5 such that S _ i starts with
i
, so he loses.
In this case, Taro the First wins.
Sample Input 2
10 catch chokudai class continue copy exec havoc intrinsic static yucatec
Sample Output 2
Second
Sample Input 3
16 mnofcmzsdx lgeowlxuqm ouimgdjxlo jhwttcycwl jbcuioqbsj mdjfikdwix jhvdpuxfil peekycgxco sbvxszools xuuqebcrzp jsciwvdqzl obblxzjhco ptobhnpfpo muizaqtpgx jtgjnbtzcl sivwidaszs
Sample Output 3
First