Description

After entering university, students need to choose courses. There are $n$ students who need to choose courses, and there are three teachers in the school: JYY, YJY, and YYJ.

In the first year, each student chose one of the teachers. After a year of study, students have formed some impressions of each other. Each student ranks the other $n - 1$ students from best to worst based on their impressions. The second-year course selection begins. Each student needs to choose a teacher, and perhaps because they have been “tricked” too many times, every student wants to switch to a different teacher. You need to schedule the students' course selections so that, among students taking the same class, the worst mutual impression is as good as possible.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain $n$ positive integers. Line $i + 1$ provides the information of student $i$. The first integer is $A_i$, which is one of $0, 1, 2$, representing the teacher chosen by student $i$ in the first year. The next $n - 1$ numbers are a permutation of $1, 2, \cdots, i - 1, i + 1, \cdots, n$, representing student $i$'s ranking of the other students from best to worst.

Output Format

Output one integer: the smallest non-negative integer $T$ such that:

• Every student chooses a different teacher from the one they chose in the first year.
• For any two students who choose the same teacher, their impressions of each other are both within the top $T$.

6
0 2 3 4 5 6
0 1 3 4 5 6
1 6 5 4 2 1
2 6 5 3 2 1
1 1 2 3 4 6
2 1 2 3 4 5

4

Hint

Sample Explanation 1

The six students chose teachers $1, 2, 0, 0, 2, 0$, respectively.

At this time, in teacher $0$'s class, student $6$ ranks student $4$ as the $4$-th best, so the answer is $T = 4$, and there is no smaller $T$.

Constraints

For $100\%$ of the testdata, $n \le 1000$.

Translated by ChatGPT 5