Problem J
Kindergarten

Photo by Lars Plougmann

Every year the three friendly teachers at the kindergarten let their classes’ kids change classes to form three new ones. Some kids, of course, are old enough to leave, but those who stay for another year are rearranged among the three teachers.

The teachers even let the kids have their say in the process. As friendship both comes and goes hastily in young years, each kid $X$ ranks every other kid $Y$ according to how glad $X$ would be to have $Y$ in her new class. In fact, $X$ produces a preference list giving a total order of the other kids, i.e. there are no such things as ties – kids she would be equally glad to have as classmates.

The three teachers do not mind if the new classes formed are unbalanced in size, since they fill up their classes with new kids about to start their first year at the kindergarten. They do, however, want all the kids in their own new class to be different from last year, since even a teacher needs a break after a whole year with the same kids. They decide that a best partition into three classes under these premises is one where no kid is in the same class as a kid not listed among the top $T$ entries on their preference list, for $T$ as small as possible. Note that the kids in a new class may very well be the same as in an old one, but then with a new teacher!

Input

The first line of input contains an integer $1\leq N \leq 200$ giving the number of kids to be rearranged at the kindergarten. The kids are numbered $1$ through $N$.

Then follow $N$ lines describing the kids. The $i$-th row first contains the identifier of their current class’ teacher (an integer $0$, $1$, or $2$), and next the $N-1$ integers $\{ 1,2,3,…,i-1,i+1,…,N\} $ in some order, describing the classmate preference list of the $i$-th kid, in descending order.

Output

The smallest non-negative integer $T$, such that there is a partitioning of the kids in three new classes such that

• no kid has the same teacher as in their current class, and

• all kids’ classmates are among the top $T$ places of their preference lists, respectively.

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

3
0 2 3
1 1 3
2 1 2

0