F - Shiritori Editorial /

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 of if equals the first character of float.
  • Taro the First chooses i=5. S _ i=takahashi, and the last character of float equals the first character of takahashi.
  • 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