Детский сад
Каждый год три дружных воспитателя в детском саду позволяют их детям поменяться группами. Но так, чтобы снова образовалось три группы. Некоторые дети становятся уже достаточно взрослыми, чтобы оставаться в саду. Но те, кто остается еще на один год, перераспределяются между тремя вопитателями.
Воспитатели даже позволяют детям сказать свое слово в процессе перераспределения. Как дружба приходит и уходит поспешно в молодые годы, так каждый ребенок X оценивает каждого другого ребенка Y в соответствии с тем, насколько X будет рад видеть Y у себя в новой группе. То есть X имеет список предпочтения, включающий всех остальных ребят. Если список содержит одинаковые значения, значит для X эти ребята являются одинаково желанными.
Три воспитателя не против, если сформированные новые группы будут не сбалансированы по количеству детей, так как в эти группы включаются также новые дети, которые лишь впервые начнут свою жизнь в детском саду. Они хотят, чтобы все дети их новой группы отличались от прошлогодних детей, так как даже воспитателю необходимо отдохнуть через год от одних и тех же детей. Разбиение детей на три группы считается лучшим, если ни один ребенок не находится в той же группе с детьми, не указанными в топ Т их списка предпочтений, причем Т должно быть как можно меньше. Обратите внимание, что дети в новой группе могут быть в том же составе что и в старой, но только с новым воспитателем!
Входные данные
Первая строка содержит количество детей n (n ≤ 200), которое следует перераспределить в детском саду. Дети пронумерованы числами от 1 до n.
Следующие n строк описывают детей. i-ая строка содержит номер текущего воспитателя (целое число 0, 1 или 2) и n − 1 целое число {1, 2, 3, ..., i−1, i+1, ..., n} в некотором порядке, задающие список предпочтения для i-го ребенка в убывающем порядке.
Выходные данные
Наименьшее неотрицательное целое T, для которого существует такое разбиение детей на три новых группы, что
ни один ребенок не имеет того же воспитателя, что и в старой группе
все друзья по новой группе для каждого ребенка находятся среди топ T мест в списке предпочтений.