A7597. [ABC139E] 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(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}$
> $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$。
输入输出样例
输入 #1
3 2 3 1 3 1 2
输出 #1
3
输入 #2
4 2 3 4 1 3 4 4 1 2 3 1 2
输出 #2
4
输入 #3
3 2 3 3 1 1 2
输出 #3
-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
可以在 $3$ 天内按如下方式安排所有比赛，满足所有条件。
- 第 $1$ 天：选手 $1$ 对 选手 $2$
- 第 $2$ 天：选手 $1$ 对 选手 $3$
- 第 $3$ 天：选手 $2$ 对 选手 $3$
这就是所需的最少天数。
### 样例解释 2
可以在 $4$ 天内按如下方式安排所有比赛，满足所有条件。
- 第 $1$ 天：选手 $1$ 对 选手 $2$，选手 $3$ 对 选手 $4$
- 第 $2$ 天：选手 $1$ 对 选手 $3$
- 第 $3$ 天：选手 $1$ 对 选手 $4$，选手 $2$ 对 选手 $3$
- 第 $4$ 天：选手 $2$ 对 选手 $4$
这就是所需的最少天数。
### 样例解释 3
无论如何安排比赛，都会违反某些条件。
- $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
可以在 $3$ 天内按如下方式安排所有比赛，满足所有条件。
- 第 $1$ 天：选手 $1$ 对 选手 $2$
- 第 $2$ 天：选手 $1$ 对 选手 $3$
- 第 $3$ 天：选手 $2$ 对 选手 $3$
这就是所需的最少天数。
### 样例解释 2
可以在 $4$ 天内按如下方式安排所有比赛，满足所有条件。
- 第 $1$ 天：选手 $1$ 对 选手 $2$，选手 $3$ 对 选手 $4$
- 第 $2$ 天：选手 $1$ 对 选手 $3$
- 第 $3$ 天：选手 $1$ 对 选手 $4$，选手 $2$ 对 选手 $3$
- 第 $4$ 天：选手 $2$ 对 选手 $4$
这就是所需的最少天数。
### 样例解释 3
无论如何安排比赛，都会违反某些条件。