← 返回题目列表

AtCoder · abc139_e

E. 联赛

中文机器翻译题面 查看原题

分数: 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

任何比赛安排都违反了某些条件。