E - 联赛

得分：500 分

题目描述

有 $N$ 个参与网球比赛的选手。我们称他们为选手 $1$，选手 $2$，$\ldots$，选手 $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。

3
2 3
1 3
1 2

3

如果比赛安排如下所示，所有条件都能够满足：

• 第 $1$ 天：选手 $1$ 对选手 $2$
• 第 $2$ 天：选手 $1$ 对选手 $3$
• 第 $3$ 天：选手 $2$ 对选手 $3$

这需要的最少天数。

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

4

如果比赛安排如下所示，所有条件都能够满足：

• 第 $1$ 天：选手 $1$ 对选手 $2$，选手 $3$ 对选手 $4$
• 第 $2$ 天：选手 $1$ 对选手 $3$
• 第 $3$ 天：选手 $1$ 对选手 $4$，选手 $2$ 对选手 $3$
• 第 $4$ 天：选手 $2$ 对选手 $4$

这需要的最少天数。

3
2 3
3 1
1 2

-1

任意的比赛安排都会违反某些条件。

由于评测机性能问题， 测试点已弱化，完整测试请前往atcoder提交