Chess Tournament#9772
Huseyn loves to watch chess. And his favorite Candidates Tournament will have players. The tournament runs in a round robin format, so N \cdot (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 -th player (1 \le i \le N) plays one game against player A_{i,1}, A_{i,2}, ..., A_{i,N-1} in this order.
If so, find the minimum number of days you need.
The first line contains number (3 \le N \le 1000), the number of players. The next lines contain N-1 numbers A_{i,j}.
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 .
Example 1
Example 2
Example 3
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.