407262: GYM102739 D Игра в города

D. Игра в городаограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Маленькая Саша любит играть с папой в города. За последние дни они уже сыграли целых $$$N$$$ партий. Каждую игру начинал папа, но выигрывала Саша. Поэтому у Саши появилось подозрение — а вдруг папа ей поддается?

У Саши очень хорошая память: она помнит всё о каждой из игр, а именно: что в игре с номером $$$i$$$ всего было названо $$$M_i$$$ городов, а также сами города в правильном порядке. Напомним, что по правилам игры, первая буква названия каждого следующего города должна совпадать с последней буквой названия предыдущего, и никакой город не может быть назван дваджы.

У папы тоже отличная память, и если в какой-либо игре был назван город, то во всех последующих партиях он будет его помнить и сможет назвать его в свой ход. Помогите Саше узнать, достаточно ли этих данных чтобы определить, поддавался ли папа (т.е. была ли такая ситуация, в которой он мог назвать известный ему по предыдущим играм город, но сдался). В случае, если папа поддался, выведите также город, который он мог бы назвать в свой следущий ход.

Входные данные

В первой строке дано одно целое число $$$n$$$ — количество партий $$$(2 \le n \le 10^5)$$$.

Далее следует описание $$$n$$$ игр.

В первой строке каждого описания содержится количество названных городов $$$m_i$$$ ($$$1 \le m_i \le 10^5$$$), а далее $$$m_i$$$ строк с названиями городов. Напомним, что в каждой партии число городов было чётным.

Название любого города содержит только латинские буквы, причём первая буква всегда заглавная, а остальные — строчные. Гарантируется, что название содержит хотя бы две буквы. Суммарная длина всех названий не превосходит $$$2 \cdot 10^5$$$ символов.

Выходные данные

Для каждой игры в отдельной строке выведите ответ на задачу: название города, которым папа мог бы сделать ход, или «unknown» (без кавычек), если в предыдущих играх подходящего города не было.

Система оценки

$$$$$$\begin{array}{|c|c|c|c|c|} \hline \text { Подзадача } & \text { Баллы } & \text { Ограничения } & \text { Оценка } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \text { подзадача } & \\ \hline 1 & 20 & n = 2, \text{суммарная длина слов} \le 500 & \text { подзадача } & \\ \hline 2 & 40 & N \le 1000, \text{суммарная длина слов} \le 10^4 & \text { подзадача } & 1 \\ \hline 3 & 40 & \text { Без дополнительных ограничений } & \text { подзадача } & 1,2 \\ \hline \end{array}$$$$$$

ПримерВходные данные

3
4
Samara
Aramavir
Rome
Erevan
2
Rostov
Vilnius
4
Anapa
Aramavir
Riga
Ankara

Выходные данные

unknown
Samara
unknown