Student Groups

KOI University's gifted education center is holding a camp for students interested in informatics. Some students at the camp already know each other.

The center will list the students by date of birth, from earliest to latest, and split this ordered list into several contiguous groups. In an ideal split, every pair of students in the same group would know each other, and every pair of students in different groups would not know each other. Since such a split is often impossible, the quality of a split is measured by the following score.

Add 1 point for each pair of students in the same group who do not know each other. Add 1 point for each pair of students in different groups who do know each other.

The figure below shows a split of 8 students into three groups A, B, and C with score 5. Black dots are students, lines are acquaintance relationships, and dashed circles are groups. The students are numbered 1 through 8 by birth-date order. There are 3 acquaintance edges between A and B and 1 between B and C. Every pair inside A and inside B knows each other, but students 7 and 8 inside C do not. The score is therefore 3+1+1=5.

Splitting the same students into two groups as below also has score 5.

Splitting them into four groups as below has score 8.

Given the acquaintance information, write a program that outputs a split with the minimum possible score. A split consisting of one group is allowed.

The first line contains N, the number of students. N is between 2 and 3,000, inclusive. Students are numbered 1 through N, and a smaller number means an earlier date of birth.

The next N lines describe acquaintance relationships. The K-th of these lines lists, in increasing order, the students known by student K, followed by 0. Values are separated by spaces. If student I knows student J, then student J also knows student I.

On the first line, output the minimum possible split score.

On the second line, output the number of groups followed by the size of each group, in order from the group containing the earliest-born students. Separate all values by spaces. If several splits have the minimum score, output any one of them.