P7210 [COCI 2020/2021 #3] Vlak

Nina and Emilija play a game on paper. At the beginning, the paper is blank. In one turn, a player appends one letter to the end of the current word on the paper. Then they alternate turns. Nina moves first. When choosing a letter, players must follow this rule: after each added letter, the resulting word must be a prefix of some word in that player’s favorite song. If a player cannot make a move on her turn, she loses. Assuming both players play optimally, determine who wins.

The first line contains a positive integer $n$, the number of words in Nina’s favorite song. The next $n$ lines each contain one word from Nina’s favorite song. The next line contains a positive integer $m$, the number of words in Emilija’s favorite song. The next $m$ lines each contain one word from Emilija’s favorite song. All input words contain only lowercase letters, and the total length of all words does not exceed $200000$.

Output the winning player, `Nina` or `Emilija`.

#### Explanation of Sample 1 If Nina first writes the letter `b`, then Emilija will be forced to write `b`, and then Nina will continue by writing `b`. The current word becomes `bbb`, and Emilija cannot make the next move, so Nina wins. If Nina first writes the letter `a`, then Emilija will write `b`. The word becomes `ab`, so Nina cannot make the next move, and she loses. #### Constraints For the $40$-point testdata, the total length of all words does not exceed $2000$. For $100\%$ of the testdata, the total length of all words does not exceed $200000$. #### Notes **This problem’s scoring follows the original COCI problem setting, with a full score of $70$.** **Translated from [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #3](https://hsin.hr/coci/contest3_tasks.pdf) _T2 Vlak_.** Translated by ChatGPT 5