Description

ZHtwinkle 召集了 $n$ 个人要举行共 $\frac{n(n-1)}{2}$ 场比赛，每个人要以一个特定的顺序与其他人比赛。

且每个人每天只可以比一场比赛，问最少比赛的天数为多少，无解输出 -1 。

Format

Input

第一行一个个数 $1 \le N \le 1000$

接下来 $N$ 行每行 $N - 1$ 个数 $1 \le A_{ij} \le N, A_{ij} \neq i$ 且保证每一行的数都互不相同代表比赛顺序，选手必须遵守比赛顺序，没有和当前对手比完无法跟其他对手比。

Output

输出一个数代表最少比赛的天数

Samples

3
2 3
1 3
1 2

3

3
2 3
3 1
1 2

-1