eolymp
bolt
Try our new interface for solving problems
Problems

Kindergarten

Kindergarten

Time limit 1 second
Memory limit 64 MiB

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 class mates.

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 data

The first line of input contains a positive integer n200 giving the number of kids to be rearranged at the kindergarden. 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 class mate preference list of the i-th kid, in descending order.

Output data

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’ class mates are among the top T places of their preference lists, respectively.

Examples

Input example #1
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
Output example #1
4
Source ACM ICPC NCPC 2012, 6th October 2012