题目描述

在友爱小学一年级的第一天，每个学生都会花一分钟时间和他或她还不认识的每个同学交谈。当学生鲍勃看到一个陌生的面孔时，他会问：“你是谁？” 一个典型的回答是：“我是查理，你是谁？” 然后鲍勃会说：“我是鲍勃！” 他们会交谈一分钟。这非常可爱。然后，在一分钟之后，他们分开，各自寻找另一个陌生人打招呼。这需要时间。在一个有 29 或 30 个互相陌生人的班级中，这需要 29 分钟；老师们认为，这段时间可以更好地用于学习字母表。当然，几乎不可能有一个一年级班级里谁都不认识谁；总有邻居和玩伴已经互相认识了，所以他们不需要再花时间互相了解。

两位一年级老师要求，为了节省时间，学生应该被分配到两个班级中，使得两个班级的大小差异最多为 1，并且完成这些介绍所需的时间尽可能短。一年级新生班级中不会有超过 60 名学生。

如何分配学生到班级呢？你的任务是编写一个程序来回答这个问题。

输入

学校记录包含关于学生友谊的信息，以数字列表的形式表示。如果有 29 名学生，那么他们用数字 1 到 29 表示。单个学生的记录首先包含他的学生编号（在本例中为 1 到 29），然后是他的熟人数，然后是一个无序的熟人列表。例如，这条记录：

17 4 5 2 14 22

表示学生 17 认识 4 名学生：5、2 等等。所有新生的记录通过将所有学生的记录连接在一起形成一个数字列表来表示。在这个格式中，空格和换行符是无关紧要的。因此，这个：

1 1 2 2 1 1

就是一个完整的数据库，表示新生班级中只有两名学生，而且他们互相认识；而这个：

1 2 3 4

2 2 3 4

3 2 1 2

4 2 1 2

表示 1 不认识 2，3 不认识 4，但其他配对都互相认识。

数据库已经经过一致性检查，因此如果 A 认识 B，那么 B 也认识 A。

输出

你的输出应该以一个数字开始，表示在最佳合法班级分配下完成介绍所需的时间。对于上面的简单两学生问题，唯一的合法答案是：

0

输入数据 1

1 2 3 4 
2 2 3 4 
3 2 1 2 
4 2 1 2 

输出数据 1

0

提示

为了使这个问题更易于处理，进行了以下更改。将恰好有两个班级。学生人数不会超过 30 人。学生将尽可能平均地分配到两个班级中。一个学生的“孤独度”是指他所在班级中他不认识的学生人数。你需要安排班级，以最小化最“孤独”的学生的孤独度。对于示例数据，你可以将 1 和 3 分到第一班，2 和 4 分到第二班，这样他们就不需要花时间互相了解了。

来源

美国中南部 1998