为展示各路棋手的高超技艺，某知名棋院决定举办一场别具一格的棋王对弈大赛。

大赛邀请了 N 位顶尖棋手参加，每位棋手拥有一个独特的编号，从 1 到 N。大赛采用单循环赛制，即每两位棋手之间将进行一场对弈，总共会有 N(N-1)/2 场对弈，确保每对棋手恰好对弈一次。

大赛的组织者需要制定一个对弈日程表，满足以下条件：

• 每日对弈安排：每天可以安排多场对弈，但每位棋手每天最多参与一场对弈。
• 对弈顺序要求：每位棋手 i（1 \leq i \leq N）都有一个期望的对弈顺序，用 A_{i,1}, A_{i,2}, \dots, A_{i,N-1} 表示。也就是说，棋手 i 希望他的第 1 场对弈是对阵棋手 A_{i,1}，第 2 场对阵棋手 A_{i,2}，依此类推，直到第 N-1 场。

你的任务是判断是否能够安排一个对弈日程，满足所有棋手的对弈顺序要求，同时保证每位棋手每天最多参与一场对弈。如果可能，计算完成所有对弈所需的最小天数；如果不可能，则输出 -1。

第一行输入一个整数 N，表示棋手的数量。

接下来 N 行，每行包含 N-1 个整数，第 i 行的第 j 个数 A_{i,j} 表示棋手 i 希望在第 j 场对弈中对阵的对手编号。

如果可以安排满足所有条件的对弈日程，输出一个整数，表示完成所有对弈所需的最小天数。

如果无法安排，输出 -1。

样例 1 说明

可以安排一个为期 3 天的对弈日程：

• 第 1 天：棋手 1 对阵棋手 3。
• 第 2 天：棋手 1 对阵棋手 2。
• 第 3 天：棋手 2 对阵棋手 3。

数据范围

对于 20\% 的数据，满足 1 \le N \le 10。

对于 40\% 的数据，满足 1 \le N \le 200。

对于 75\% 的数据，满足 1 \le N \le 500。

对于 100\% 的数据，满足 3 \leq N \leq 1000，1 \leq A_{i,j} \leq N，A_{i,j} \neq i（棋手不会与自己对弈），对于每个 i，A_{i,1}, A_{i,2}, \dots, A_{i,N-1} 各不相同（每个棋手的对手列表无重复）。

月赛拓扑排序25年4月