Huseyn loves to watch chess. And his favorite Candidates Tournament will have N players. The tournament runs in a round robin format, so N*(N-1)/2 games will be played. Is it possible to organize the scheduling of these parties so as to meet certain conditions?

• Each player must play at least one game a day.
• Each i - th player (1 <= i <= N) plays one game against player Ai[1], Ai[2]....,A [i][N-1]in this queue

If so, find the minimum number of days you need.

Input data

The first line contains number N (3 ≤ N ≤ 1000), the number of players. The next N lines contain N-1 numbers Ai[j].

Output

If it is possible to schedule all matches so that all conditions are completed, output the minimum number of days that is required; if this is not possible, print -1.

Explanations:

In the first test, all conditions can be met if matches are scheduled for three days as follows:

• Day 1: Player 1 vs. Player 2
• Day 2: Player 1 vs. Player 3
• Day 3: Player 2 vs. Player 3 This is the minimum number of days required.

In the third test, any match planning violates some conditions.