Background

众多鼠美眉为了赢得爱情之神$kunkka$的芳心, 决定进行群体$PK$.

Description

现在有$n$名鼠美眉, 两两之间进行$PK$, 一共会举行$\frac{n(n-1)}{2}$场比赛, 每个人都会有一个特定的$PK$顺序, 每人每天只可以进行一场$PK$, 现在$kunkka$想知道, 鼠美眉们至少需要比赛的天数是多少?

如果无法正常进行比赛, 则输出$-1$.

Format

Input

第一行一个整数$n$.

接下来$n$行, 每行输入$n-1$个整数$a_{ij}$, 表示$i$选手的$PK$对手.

注意: 选手必须按照比赛顺序参赛, 不可以调整比赛顺序.

Output

输出一个整数, 表示最少比赛的天数, 如果无解则输出-1

Samples

3
2 3
1 3
1 2

3

样例1解释

一共3个人PK, 第1天(1, 2), 第2天(1, 3), 第3天(2, 3)

3
2 3
3 1
1 2

-1

Limitation

1s, 1024KiB for each test case.

$1 <= n <= 1000$