Lonely
Scenario
On the first day of first grade at Friendly Elementrary School, every student
has to indroduce himself or herself to every classmate whom he or she does
not already know. 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. The ``loneliness'' of a student is the number of students
in his or her class whom he or she does not initially know. The two
first-grade teachers have requested that students be allocated to their
two classes so that to minimize the loneliness of the loneliest student.
There are no more than 30 students. How can the assignment of students
to classes be made? Your job is to write the software that answers
the question.
Input: lonely.in
The school records include information about these student friendships,
represented as lists of numbers. If there are 29 students, then they
are represented by the numbers 1 to 29. The record for a single student
includes, first, his/her student identification number (1 to 29, in this
example), 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 records for all the students in the incoming class are represented
as the list of numbers that results from concatenating all the student
records together. Spaces and line breaks are irrelevent in this format.
Thus, this
1 1 2 2 1 1
is a whole database, indicating that there are only two students in
the incoming class, and they know each other; and this
1 2 3 4
2 2 3 4
3 2 1 2
4 2 1 2
indicates that 1 doesn't know 2, and 3 doesn't know 4, but all other
pairs know each other.
The database has been checked for consistency, so that if A knows B,
then B knows A.
Output: lonely.out
Your output should give the class enrollment that minimizes the loneliness
of the loneliest student. Specifically, you should output all students
enrolled into one of the two classes (which impliess the enrollment into
the other class).
Sample Input
1 2 3 4
2 2 3 4
3 2 1 2
4 2 1 2
Sample Output
1 3