The original version of Shiritori is played using Japanese
hiragana, katakana, or kanji characters. Source
WikiMedia
The Japanese game of Shiritori is the perfect 2-player game
for a long car ride. The rules are simple: the first player
picks any word to say, then the second player must choose a new
word that begins with the last letter of the word that the
first player just said. Then it is the first player’s turn
again to say a word that begins with the last letter of the
previous word the second player said, and so on. At each turn,
the player whose turn it is must say a word that links to the
previous one and which has not been called out before
during the game. Your job is to determine if the game was
played according to these rules, given a history of the words
used in a particular game. In a game, player $1$ always starts first.
Input
Input consists of one test case that begins with an integer
$N$ ($2 \leq N \leq 100\, 000$) on a single
line. Each of the following $N$ lines contains $1$ word. The words are presented in
the order in which the players called them out, starting with
player $1$. All words
consist of between $1$ and
$120$ lowercase English
letters.
Output
If the game was played according to the rules, output
“Fair Game”. Otherwise, find out
which player first violated the rules of the game. That player
lost the game, so output “Player <i>
lost”. For example, if player $1$ violated the rules first, output
“Player 1 lost”.
| Sample Input 1 |
Sample Output 1 |
5
apple
ear
real
letters
style
|
Fair Game
|
| Sample Input 2 |
Sample Output 2 |
3
apple
extra
apple
|
Player 1 lost
|
| Sample Input 3 |
Sample Output 3 |
2
apple
neat
|
Player 2 lost
|
| Sample Input 4 |
Sample Output 4 |
5
apple
east
team
meat
team
|
Player 1 lost
|
