网球比赛日程

题目描述

有 $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}$ 的顺序，与这些选手各比赛一次。

输入格式

输入按以下格式从标准输入给出：

$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

在 $3$ 天内按如下方式比赛即可满足所有条件：

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

这就是所需的最少天数。

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

4

在 $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

无论怎样安排比赛日程，都会违反某种条件。

数据范围

• $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}$ 互不相同