Background

新一届的骑士锦标赛又开始了

Description

本次比赛有 n 位骑士参加，采用循环赛的赛制，每人每天最多进行一场比赛，一场比赛只能选一名对手进行单挑

每位骑士都会进行 n−1 场比赛，他们每人都可以为自己未来的对手安排一个挑战的顺序，所有人的要求都会被满足

请你计算最少的比赛天数是多少，若无法满足所有人的要求，输出 −1

Format

Input

第一行输入一个 n ，代表骑士数量

接下来 n 行每行输入 n-1 个数表示该骑士要单挑的对手编号顺序(编号 1~n )

2<n<1000

Output

输出最少比赛天数，无解则输出 -1

Samples

3
2 3
1 3
1 2

3

Limitation

1s, 1024KiB for each test case.