题目描述

有 $N$ 位棋手，每两位棋手恰好进行一场比赛。每天每位棋手最多参加一场比赛。

第 $i$ 位棋手给出了一个长度为 $N-1$ 的对手顺序 $A_{i,1},A_{i,2},\ldots,A_{i,N-1}$，表示他希望依次在第 $1$ 场、第 $2$ 场直至第 $N-1$ 场比赛中面对的对手。

请判断能否同时满足所有棋手的顺序要求。若可以，输出完成全部比赛所需的最少天数；否则输出 $-1$。

输入格式

第一行包含一个整数 $N$。

接下来 $N$ 行，第 $i$ 行包含 $N-1$ 个整数，表示第 $i$ 位棋手的对手顺序。

输出格式

若存在满足所有要求的赛程，输出最少天数；否则输出 $-1$。

样例

3
3 2
1 3
1 2

3

数据范围与提示

• $3\le N\le1000$
• $1\le A_{i,j}\le N$
• $A_{i,j} e i$
• 每行的 $N-1$ 个对手编号互不相同