题目描述

有 $N$ 名选手参加网球比赛，我们将他们称为 Player $1$，Player $2$，$\\ldots$，Player $N$。

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

• 每个选手每天最多进行一场比赛。
• 对于每个选手 $i$ $(1 \\leq i \\leq N)$，按照顺序与选手 $A_{i, 1}, A_{i, 2}, \\ldots, A_{i, N-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}$ 两两不同。

输入

输入以标准格式给出，格式如下：

$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

3
2 3
1 3
1 2

示例输出 1

3

如果比赛按照以下方式安排三天，则满足所有条件：

• 第一天：Player $1$ vs Player $2$
• 第二天：Player $1$ vs Player $3$
• 第三天：Player $2$ vs Player $3$

这是所需的最少天数。

示例输入 2

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

示例输出 2

4

如果比赛按照以下方式安排四天，则满足所有条件：

• 第一天：Player $1$ vs Player $2$，Player $3$ vs Player $4$
• 第二天：Player $1$ vs Player $3$
• 第三天：Player $1$ vs Player $4$，Player $2$ vs Player $3$
• 第四天：Player $2$ vs Player $4$

这是所需的最少天数。

示例输入 3

3
2 3
3 1
1 2

示例输出 3

-1

任何比赛安排都会违反某个条件。