Background

Special for beginners, ^_^

Description

睿爸附小想办一场乒乓球循环赛。

每名参赛选手和其他选手对战一场，并且指定了与其他选手的对战顺序。

每名选手每天最多只打一场比赛。

问最少需要多少天可以打完全部比赛。

Format

Input

第一行一个正整数 $n（2<n\le1000）$，表示选手的数量。

后面每行给出从选手 1 到选手 $n$ 希望和其他选手对战的顺序。

保证第 $i$ 个选手的顺序列表是 $1$ ~ $n$ 的某个全排列删除 $i$ 后得到的序列。

Output

如果可行，输出完成所有比赛的最少天数。否则输出 -1 。

Samples

3
2 3
1 3
1 2

3

3
2 3
3 1
1 2

-1