题目描述

有 $N$ 个参与网球比赛的选手。我们称他们为选手 $1$，选手 $2$,...，选手 $N$ 比赛采用循环赛制，总共有 $N(N - 1)/2$ 场比赛。 能否安排这些比赛，使得满足以下所有条件?如果可以，请同时找到所需的最少天数。 每个选手一天最多进行一场比赛。

每个选手$i(1 \leq i \leq N)$按照顺序与选手 $A_{i,1},A_{i,2}...A_{i,N-1}$ 一对一进行比赛。

输入

第一行输入一个整数$N$

输入一个矩阵$N \times 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

样例解释

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

提示

$3 \leq N \leq 1000$

$1 \leq A_{i,j} \leq N$

$A_{i,j} \neq i$

$A_{i,1},A_{i,2}...A_{i,N-1}$

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