On the first day of first grade at Friendly Elementrary School, it is customary for each student to spend one minute talking to every classmate that he or she does not already know. When student Bob sees an unfamilar face, he says “You who?” A typical response is “Me Charlie, you who?” Then Bob says, “Me Bob!” and they talk for a minute. It’s very cute. Then, after a minute, they part and each looks for another stranger to greet. This takes time. In class of twenty-nine or thirty mutual strangers, it takes 29 minutes; time that, according to teachers, could be better spent learning the alphabet. Of course, it is rare to have a first grade class where nobody knows anyone else; there are neighbors and playmates who already know each other, so they don’t have to go through the get-to-know-you minutes with each other. The two first grade teachers have requested that, to save time, students be allocated to their two classes so that the difference in the sizes of the classes is at most one, and the time it takes to complete these introductions is as small as possible. There are no more than 24 students in the incoming first grade class. How can the assignment of students to classes be made? Your job is to write the software that answers the question. Input The input data consists of a number of test cases. Subsequent cases are separated by a single blank line. The descriptions of the test cases follow. The first line of a test case description contains one integer N (1 ≤ N ≤ 24), denoting the total number students. Each of the next N lines contains the record about one student’s friendships, represented as lists of numbers. If there are N students, then they are represented by the numbers 1 to N. The record for a single student includes, first, his/her student identification number (1 to N), then the number of his/her acquaintances, then a list of them in no particular order. So, for example, this record 17 4 5 2 14 22 indicates that student 17 knows 4 students: 5, 2, 14 and 22. The following test case 4 1234 2234 3212 4212 indicates that 1 doesn’t know 2, and 3 doesn’t know 4, but all other pairs know each other. The input data has been checked for consistency, so that if A knows B, then B knows A. Output For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. Your output for each case should contain three lines. In the first line there should be the maximal number of introductions per person in the best possible legal class assignment. The second and third
2/2 lines describe the two class enrollments that achieves that bound. An enrollment for each class is represented by the number of students in the class, and then a list of the students in the class, in increasing order separated by single spaces. If there is more than one such assignment, anyone will do. Sample Input 4 1234 2234 3212 4212 2 112 211 Sample Output 0 213 224 0 11 12