Шаховий турнір

Обмеження на час виконання 1 секунда

Обмеження на використання пам'яті 64 мегабайти

Гусейн обожнює дивитися шахи. І в його улюбленому шаховому турнірі претендентів буде грати N гравців. Турнір проходить у круговому форматі, тому буде зіграно N(N-1)/2* партій. Чи можливо організувати розклад цих партій так, щоб відповідати певним умовам?

Кожен гравець повинен зіграти хоча б одну партію в день.
Кожен i-ий гравець ( 1 ≤ i ≤ N ) грає одну партію проти гравця A[i][1], A[i][2]...., A[i][N-1] у такій послідовності.

Якщо так, то знайдіть мінімальну кількість днів, яка потрібна.

Вхідні дані

Перший рядок містить число N ( 3 ≤ N ≤ 1000), кількість гравців.Наступні N рядків містять по N-1 чисел A[i][j].

Вихідні дані

Якщо можна запланувати всі матчі так, щоб усі умови були виконані, виведіть мінімальну кількість днів, яка потрібна; якщо це неможливо, виведіть -1.

Приклади

Вхідні дані #1

Відповідь #1

Вхідні дані #2

Відповідь #2

Вхідні дані #3

Відповідь #3

Примітка

У першому тесті всі умови можуть бути виконані, якщо матчі заплановані на три дні наступним чином:

День 1: Гравець 1 проти Гравця 2
День 2: Гравець 1 проти Гравця 3
День 3: Гравець 2 проти Гравця 3Це мінімальна кількість необхідних днів.

У третьому тесті будь-яке планування матчів порушує деякі умови.

Відправки 1