atcoder#ABC278F. [ABC278F] Shiritori

[ABC278F] Shiritori

Score : 500500 points

Problem Statement

You are given NN strings S1,S2,,SNS _ 1,S _ 2,\ldots,S _ N. Si (1iN)S _ i\ (1\leq i\leq N) is a non-empty string of length at most 1010 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 (1iN)i\ (1\leq i\leq N), which should satisfy the following two conditions:

  • ii 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 SjS_j equals the first character of SiS_i, where jj is the last integer chosen.

The player who is unable to choose a conforming ii loses; the other player wins.

Determine which player will win if the two players play optimally.

Constraints

  • 1N161 \leq N \leq 16
  • NN is an integer.
  • Si (1iN)S _ i\ (1\leq i\leq N) is a non-empty string of length at most 1010 consisting of lowercase English letters.
  • SiSj (1i<jN)S _ i\neq S _ j\ (1\leq i\lt j\leq N)

Input

The input is given from Standard Input in the following format:

NN

S1S_1

S2S_2

\vdots

SNS_N

Output

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

6
enum
float
if
modint
takahashi
template
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=3i=3. Si=S _ i=if.
  • Jiro the Second chooses i=2i=2. Si=S _ i=float, and the last character of if equals the first character of float.
  • Taro the First chooses i=5i=5. Si=S _ i=takahashi, and the last character of float equals the first character of takahashi.
  • Jiro the Second is unable to choose i2,3,5i\neq2,3,5 such that SiS _ i starts with i, so he loses.

In this case, Taro the First wins.

10
catch
chokudai
class
continue
copy
exec
havoc
intrinsic
static
yucatec
Second
16
mnofcmzsdx
lgeowlxuqm
ouimgdjxlo
jhwttcycwl
jbcuioqbsj
mdjfikdwix
jhvdpuxfil
peekycgxco
sbvxszools
xuuqebcrzp
jsciwvdqzl
obblxzjhco
ptobhnpfpo
muizaqtpgx
jtgjnbtzcl
sivwidaszs
First