ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1551. Турнир по сумо

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В Токио проходит турнир по сумо, в котором участвуют 2N спортсменов. В каждом поединке обязательно есть победитель, а проигравший выбывает из турнира. Таким образом, чтобы определить победителя турнира, необходимо провести N раундов.
Организаторы хотят, чтобы в как можно большем числе раундов все поединки прошли между сумоистами из разных префектур Японии. Для этого они могут подтасовать результаты жеребьевки произвольным образом.

Исходные данные

В первой строке записано число N (1 ≤ N ≤ 10). В каждой из следующих 2N строк записаны имя сумоиста и префектура, которую он представляет. Имя и префектура являются последовательностями латинских букв длиной не более 30.

Результат

Выведите максимальное количество раундов, в которых сумоисты из одной префектуры гарантированно не встретятся (то есть найдите наибольшее возможное число K, такое, что при какой-то начальной расстановке соперников, независимо от исхода поединков, по крайней мере в K раундах все поединки будет сыграны между сумоистами из разных префектур).

Пример

исходные данныерезультат
3
Homasho Ishikawa
Tamakasuga Tokyo
Futeno Tochigi
Takekaze Tokyo
Kasugao Yamaguchi
Kotoshogiku Ishikawa
Kotomitsuki Tokyo
Miyabiyama Shizuoka
1
Автор задачи: Сергей Пупырев
Источник задачи: XI командный чемпионат Урала по спортивному программированию, Екатеринбург, 21 апреля 2007 г