Score : $500$ points

问题描述

给定 $N$ 个字符串 $S _1,S _2,\ldots,S _N$。其中，$S _i\ (1\leq i\leq N)$ 是一个长度不超过 10 的非空小写英文字符组成的字符串，并且这些字符串两两不相同。

太郎一号和次郎二号玩一个单词接龙游戏。在这个游戏中，两位玩家交替进行回合，由太郎一号先行。在每个玩家的回合中，玩家选择一个整数 $i\ (1\leq i\leq N)$，该整数必须满足以下两个条件：

• 自游戏开始以来，$i$ 与两位玩家之前所选择的所有整数都不同；
• 当前是游戏的第一回合，或者 $S_j$ 的最后一个字符等于 $S_i$ 的第一个字符，其中 $j$ 是上一回合所选择的整数。

如果玩家无法选择一个符合上述条件的整数，则该玩家输掉比赛；另一玩家获胜。

请判断当两位玩家均采取最优策略时，哪位玩家将会赢得比赛。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 11:43:03