分数: 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.
示例输入 1
3 2 3 1 3 1 2
示例输出 1
3
如果比赛安排在三天内,则可以满足所有条件,如下:
- 天 1:玩家 1 vs 玩家 2
- 天 2:玩家 1 vs 玩家 3
- 天 3:玩家 2 vs 玩家 3
这是所需的最少天数。
示例输入 2
4 2 3 4 1 3 4 4 1 2 3 1 2
示例输出 2
4
如果比赛安排为四天,则可以满足所有条件,如下所示:
- 天 1:玩家 1 vs 玩家 2,玩家 3 vs 玩家 4
- 天 2:玩家 1 vs 玩家 3
- 天 3:玩家 1 vs 玩家 4,玩家 2 vs 玩家 3
- 天 4:玩家 2 vs 玩家 4
这是所需的最少天数。
示例输入 3
3 2 3 3 1 1 2
示例输出 3
-1
任何比赛安排都违反了某些条件。