题目描述

Farmer John想要举办一次奶牛运动会，现在有$N$头奶牛报名参加，编号为$1 \dots N$。

Farmer John 的要求如下：

• 每头牛每天只能比赛一场；

• 比赛采用循环赛制，第$i$头牛的对手顺序，必须按照在报名的时候选择的顺序:$a_{i,1},a_{i,2} \dots a_{i,N-1}$。

如果可以能够按照要求完成所有比赛，请输出最少比赛的天数，如果不能完成，请输出-1.

输入格式

第一行一个整数$N$ ，接下来$N$行，每行$N-1$个整数，表示第$i$ 头牛选定的比赛顺序。

$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}$

输出格式

一个整数，表示答案。

样例数据

input

3

2 3

1 3

1 2

output

3

第一天，1号对2号，第二天，1号对3号，第三天 2号对3号，比赛全部完成。

input

4

2 3 4

1 3 4

4 1 2

3 1 2

output

4

input

3

2 3

3 1

1 2

output

-1

数据规模与约定

本题采用subtask捆绑评测。

30% 保证 $2 \leq N \leq 10$

60% 保证 $2 \leq N \leq 500$

100% 保证 $2 \leq N \leq 1000$

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$