#abc278f. [abc278_f]Shiritori

[abc278_f]Shiritori

问题陈述

给定 NN 个字符串 S1,S2,ldots,SNS _ 1,S _ 2,\\ldots,S _ N。其中 Si(1leqileqN)S _ i\\ (1\\leq i\\leq N) 是由小写英文字母组成的非空字符串,且这些字符串两两不相同。

甲和乙在进行一个单词链游戏。在这个游戏中,两位玩家轮流行动,甲先行动。在每位玩家的回合中,玩家选择一个整数 i(1leqileqN)i\\ (1\\leq i\\leq N),该整数需要满足以下两个条件:

  • ii 与当前游戏开始后两位玩家选择的整数不同;
  • 如果当前回合是游戏开始的第一回合,或者 SjS_j 的最后一个字符等于 SiS_i 的第一个字符,其中 jj 是上一个选择的整数。

无法找到满足条件的整数 ii 的玩家输,另一位玩家获胜。

请确定在两位玩家都以最优策略行动时,哪位玩家将获胜。

约束条件

  • 1leqNleq161 \\leq N \\leq 16
  • NN 是整数。
  • Si(1leqileqN)S _ i\\ (1\\leq i\\leq N) 是由小写英文字母组成的非空字符串。
  • SineqSj(1leqiltjleqN)S _ i\\neq S _ j\\ (1\\leq i\\lt j\\leq N)

输入

从标准输入读入数据,输入格式如下:

NN S1S_1 S2S_2 vdots\\vdots SNS_N

输出

如果甲以最优策略获胜,则输出 First;如果乙以最优策略获胜,则输出 Second


示例输入 1

6
enum
float
if
modint
takahashi
template

示例输出 1

First

例如,游戏的进行方式如下所示。请注意,该示例中的两位玩家可能没有采用最优策略。

  • 甲选择 i=3i=3Si=S _ i=if
  • 乙选择 i=2i=2Si=S _ i=float,且 if 的最后一个字符等于 float 的第一个字符。
  • 甲选择 i=5i=5Si=S _ i=takahashi,且 float 的最后一个字符等于 takahashi 的第一个字符。
  • 乙无法选择一个满足 SiS _ ii 开头的整数,因此他输了。

在这种情况下,甲获胜。


示例输入 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