Гусейн обожает смотреть шахматы . И в его любимом шахматном турнире претендентов будет играть N игроков . Турнир идет в круговом формате ,поэтому будет сыграно N*(N-1)/2 партий . Возможно ли организовать рассписание этих партий так ,чтобы соответствовать некоторым условиям ?

• Каждый игрок должен сыграть хотя-бы одну партию в день .
• Каждый i-ый игрок ( 1 <= i <= N ) играет одну партию против игрока Ai[1] , Ai[2]...., Ai[N-1] в такой очереди

Если да ,то найдите минимальное количество дней ,которое нужно .

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

Первая строка содержит число N ( 3 ≤ N ≤ 1000) , количество игроков. Следующие N строк содержит по N-1 чисел Ai[j].

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

Если можно запланировать все матчи так, чтобы все условия были выполнены, выведите минимальное количество дней, которое требуется; если это невозможно, выведите -1.

Пояснения:

В первом тесте все условия могут быть выполнены, если матчи запланированы на три дня следующим образом:

• День 1: Игрок 1 против Игрока 2
• День 2: Игрок 1 против Игрока 3
• День 3: Игрок 2 против Игрока 3 Это минимальное количество необходимых дней.

В третьем тесте любое планирование матчей нарушает некоторые условия.