当前没有测试数据。

题目描述

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

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

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

• 每日对弈安排：每天可以安排多场对弈，但每位棋手每天最多参与一场对弈。
• 对弈顺序要求：每位棋手 $i$（$1 \le i \le N$）都有一个期望的对弈顺序，用 $A_{i,1}, A_{i,2}, …, 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
3 2
1 3
1 2

输出

3

数据范围

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

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

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

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