Problem8243--ABC278 —— F - Shiritori

8243: ABC278 —— F - Shiritori

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 2Submit Num: 2StatisticsShowOff!

Description

You are given N strings $S_1,S_2,…,S_N$. $S_i\ (1≤i≤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≤i≤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.

Input

The input is given from Standard Input in the following format:
$N$
$S_1$
$S_2$
$⋮$
$S_N$

Output

Print First if Taro the First wins when the two players play optimally; print Second if Jiro the Second wins.

Constraints

$1≤N≤16$
N is an integer.
$S_i\ (1≤i≤N)$ is a non-empty string of length at most 10 consisting of lowercase English letters.
$S_i\neq S_j\ (1≤i<j≤N)$

Sample 1 Input 

6
enum
float
if
modint
takahashi
template

Sample 1 Output 

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≠2,3,5 such that $S_i$ starts with i, so he loses.

In this case, Taro the First wins.

Sample 2 Input 

10
catch
chokudai
class
continue
copy
exec
havoc
intrinsic
static
yucatec

Sample 2 Output 

Second

Sample 3 Input 

16
mnofcmzsdx
lgeowlxuqm
ouimgdjxlo
jhwttcycwl
jbcuioqbsj
mdjfikdwix
jhvdpuxfil
peekycgxco
sbvxszools
xuuqebcrzp
jsciwvdqzl
obblxzjhco
ptobhnpfpo
muizaqtpgx
jtgjnbtzcl
sivwidaszs

Sample 3 Output 

First

Source/Category

 
Submit