{"problem":{"name":"Shiritori","description":{"content":"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 distin","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc278_f"},"statements":[{"statement_type":"Markdown","content":"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.\nTaro 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:\n\n*   $i$ is different from any integer chosen by the two players so far since the game started;\n*   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.\n\nThe player who is unable to choose a conforming $i$ loses; the other player wins.\nDetermine which player will win if the two players play optimally.\n\n## Constraints\n\n*   $1 \\leq N \\leq 16$\n*   $N$ is an integer.\n*   $S _ i\\ (1\\leq i\\leq N)$ is a non-empty string of length at most $10$ consisting of lowercase English letters.\n*   $S _ i\\neq S _ j\\ (1\\leq i\\lt j\\leq N)$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$S_1$\n$S_2$\n$\\vdots$\n$S_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc278_f","tags":[],"sample_group":[["6\nenum\nfloat\nif\nmodint\ntakahashi\ntemplate","First\n\nFor example, the game progresses as follows. Note that the two players may not be playing optimally in this example.\n\n*   Taro the First chooses $i=3$. $S _ i=$`if`.\n*   Jiro the Second chooses $i=2$. $S _ i=$`float`, and the last character of `if` equals the first character of `float`.\n*   Taro the First chooses $i=5$. $S _ i=$`takahashi`, and the last character of `float` equals the first character of `takahashi`.\n*   Jiro the Second is unable to choose $i\\neq2,3,5$ such that $S _ i$ starts with `i`, so he loses.\n\nIn this case, Taro the First wins."],["10\ncatch\nchokudai\nclass\ncontinue\ncopy\nexec\nhavoc\nintrinsic\nstatic\nyucatec","Second"],["16\nmnofcmzsdx\nlgeowlxuqm\nouimgdjxlo\njhwttcycwl\njbcuioqbsj\nmdjfikdwix\njhvdpuxfil\npeekycgxco\nsbvxszools\nxuuqebcrzp\njsciwvdqzl\nobblxzjhco\nptobhnpfpo\nmuizaqtpgx\njtgjnbtzcl\nsivwidaszs","First"]],"created_at":"2026-03-03 11:01:13"}}