Kindergarten

Time limit1sMemory limit128 MB

Summary

Split n students into three classes so nobody keeps their old teacher and every classmate sits in each other's top T, minimizing T.

Level: Hard9 of 10
Topics: Graph, Binary search, Greedy, Implementation
Solved: No attempts yet

Problem

A kindergarten has three teachers, and each teacher is in charge of one class. When a new semester begins, the students must be split into these three classes.

Friendships are taken into account when forming the classes. Every student has submitted a list of the other students, written in order of preference; this order is also the order in which they would like to be placed in the same class.

The classes do not have to be the same size, because new students arrive every year to fill the empty seats. However, no teacher will ever be in charge of a student they had last year.

The goal is to assign every student to a class different from last year's so that, in each class, whenever you look at the preference list submitted by any student of that class, all of the other students in the same class appear within that student's top $T$ . Make $T$ as small as possible.

Input

The first line contains the number of students $n$ $(1 \le n \le 200)$ . Students are numbered from $1$ to $n$ .

Each of the next $n$ lines describes one student. The first integer on the line is the teacher who was in charge of that student last year, which is one of $0$ , $1$ , or $2$ . It is followed by $n-1$ integers: the numbers of all students except this one, listed in that student's order of preference.

Output

Print the smallest non-negative integer $T$ that satisfies both of the following conditions:

No student is assigned to the class of the teacher who was in charge of them last year.
In each class, for the preference list submitted by any student of that class, all of the other students in the same class appear within the top $T$ .

Examples2

Example 1

Input

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

Expected output

Example 2
Input
```
3
0 2 3
1 1 3
2 1 2
```
Expected output
```
0
```