B. Спортивный турнир
Ограничение времени
2 секунды
Ограничение памяти
256Mb
Ввод
стандартный ввод или input.txt
Вывод
стандартный вывод или output.txt
Пока Маша была в отпуске, её коллеги организовали турнир по шахматам по олимпийской системе. За отдыхом Маша не обращала особого внимания на эту затею, так что она еле может вспомнить, кто с кем играл (про порядок игры даже речи не идёт). Внезапно Маше пришла в голову мысль, что неплохо бы привезти из отпуска сувенир победителю турнира. Маша не знает, кто победил в финальной игре, но сможет без труда вычислить, кто в нём играл, если только она правильно запомнила играющие пары. Помогите ей проверить, так ли это, и вывести возможных кандидатов в победители.
Формат ввода
В первой строке находится целое число k, 2≤k≤16, — количество этапов турнира. В последующих n=2k−1 строках — по две фамилии игроков (латинскими заглавными буквами) через пробел. Все фамилии уникальны, однофамильцев среди коллег нет.
Формат вывода
«NO SOLUTION» (без кавычек) — если Маша неправильно запомнила игры и по этой сетке нельзя получить турнир по олимпийской системе. Если турнирная сетка возможна, выведите две фамилии в одной строке — фамилии кандидатов на первое место (порядок не важен).
Пример 1
Ввод
Вывод
3
GORBOVSKII ABALKIN
SIKORSKI KAMMERER
SIKORSKI GORBOVSKII
BYKOV IURKOVSKII
PRIVALOV BYKOV
GORBOVSKII IURKOVSKII
IURKOVSKII KIVRIN
IURKOVSKII GORBOVSKII
Пример 2
Ввод
Вывод
2
IVANOV PETROV
PETROV BOSHIROV
BOSHIROV IVANOV
NO SOLUTION