题目描述

$N$ players will participate in a tennis tournament. We will call them Player $1$, Player $2$, $\ldots$, Player $N$.

The tournament is round-robin format, and there will be $N(N-1)/2$ matches in total. Is it possible to schedule these matches so that all of the following conditions are satisfied? If the answer is yes, also find the minimum number of days required.

• Each player plays at most one matches in a day.
• Each player $i$ $(1 \leq i \leq N)$ plays one match against Player $A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1}$ in this order.

$N$ 名选手将参加一场网球比赛。我们称他们为球员 $1$ 、球员 $2$ 、 $\ldots$ 、球员 $N$ 。

比赛采用循环赛制，总共有 $N(N-1)/2$ 场比赛。能否在安排这些比赛时满足以下所有条件？如果答案是肯定的，请找出所需的最少天数。

• 每位棋手每天最多进行一场比赛。
• 每位棋手 $i$ $(1 \leq i \leq N)$ 每天最多进行一场比赛。 $(1 \leq i \leq N)$ 与棋手 $A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1}$ 依次进行一场比赛。

输入格式

输入内容按以下格式标准输入：

$N$
$A_{1, 1}$ $A_{1, 2}$ $\ldots$ $A_{1, N-1}$
$A_{2, 1}$ $A_{2, 2}$ $\ldots$ $A_{2, N-1}$
$:$
$A_{N, 1}$ $A_{N, 2}$ $\ldots$ $A_{N, N-1}$

输出格式

如果可以安排所有匹配，从而满足所有条件，则打印所需的最少天数；如果不可能，则打印 -1。

样例 #1

样例输入 #1

3
2 3
1 3
1 2

样例输出 #1

3

样例 #2

样例输入 #2

4
2 3 4
1 3 4
4 1 2
3 1 2

样例输出 #2

4

样例 #3

样例输入 #3

3
2 3
3 1
1 2

样例输出 #3

-1

说明

数据规模与约定

• $3 \leq N \leq 1000$
• $1 \leq A_{i, j} \leq N$
• $A_{i, j} \neq i$
• $A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1}$ 都是不同的。

样例 $1$ 解释

如果比赛安排在三天内进行，则所有条件都可以满足，具体如下

• 第 $1$ 天：棋手 $1$ 对棋手 $2$ 。
• 第 $2$ 天： 棋手 $1$ 对棋手 $1$ 对棋手 $3$ 。
• 第 $3$ 天：第 $3$ 天：棋手 $2$ 对棋手 $3$ 。

这是最低天数要求。

样例 $2$ 解释

如果将比赛安排在四天内进行，则所有条件都能满足，如下所示：

• 第 $1$ 天：棋手 $1$ 对棋手 $2$ ，棋手 $3$ 对棋手 $4$ 。
• 第 $2$ 天：玩家 $1$ 对玩家 $3$ 。
• 第 $3$ 天：玩家 $1$ 对玩家 $4$ ，玩家 $2$ 对玩家 $3$ 。
• 第 $4$ 天：棋手 $2$ 对棋手 $4$ 。

这是最低天数要求。

样例 $3$ 解释

任何匹配的调度都违反了某些条件。