题目描述

$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 を出力せよ。

题目大意

n 个人进行 $\frac {n(n -1)} {2}$ 场比赛，每个人都要以一个特定的顺序与其他人比赛。

且每个人每天只可以比一场比赛，问最少比赛的天数为多少，无解输出 $-1$ 。

3
2 3
1 3
1 2

3

4
2 3 4
1 3 4
4 1 2
3 1 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}$ はすべて異なる。

Sample Explanation 1

$3$ 日間で次のように試合を行えばすべての条件を満たせます。 - $1$ 日目: 選手 $1$ 対 選手 $2$ - $2$ 日目: 選手 $1$ 対 選手 $3$ - $3$ 日目: 選手 $2$ 対 選手 $3$ これが必要な最小日数です。

Sample Explanation 2

$4$ 日間で次のように試合を行えばすべての条件を満たせます。 - $1$ 日目: 選手 $1$ 対 選手 $2$、選手 $3$ 対 選手 $4$ - $2$ 日目: 選手 $1$ 対 選手 $3$ - $3$ 日目: 選手 $1$ 対 選手 $4$、選手 $2$ 対 選手 $3$ - $4$ 日目: 選手 $2$ 対 選手 $4$ これが必要な最小日数です。

Sample Explanation 3

どのような日程で試合を行っても何らかの条件に違反します。