配点 : $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

$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

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