League

题目描述

$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

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}$ 两两不同。如果将比赛安排如下，所有条件都可以在三天内满足：

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

这是所需的最少天数。
如果将比赛安排如下，所有条件都可以在四天内满足：

第 $1$ 天：选手 $1$ 对阵 选手 $2$, 选手 $3$ 对阵 选手 $4$ 第 $2$ 天：选手 $1$ 对阵 选手 $3$ 第 $3$ 天：选手 $1$ 对阵 选手 $4$, 选手 $2$ 对阵 选手 $3$ 第 $4$ 天：选手 $2$ 对阵 选手 $4$

这是所需的最少天数。
任何其他安排都会违反某些条件。

标签: AtCoder|abc139E

来源

AtCoder|abc139E