题目描述

Jamie 是一个非常受欢迎的女孩，有很多朋友，因此她的手机通讯录总是很长。浏览整个通讯录查找朋友的号码往往需要很长时间。作为 Jamie 最好的朋友和编程天才，你建议她将通讯录分组，并最小化最大组的大小，以便更轻松地在组中搜索朋友的号码。Jamie 接受了你的建议，并给了你她的整个通讯录，包括朋友的名字、希望的组数，以及每个朋友可以属于的组。你的任务是编写程序，将列表组织成若干组，使得每个朋友只属于一个组，并且最大组的大小最小。

输入格式

• 最多20个测试用例。每个用例以两个整数$N$和$M$开头，其中$N$是通讯录长度，$M$是组数。
• 接下来$N$行，每行包含一个朋友的名字和该朋友可以属于的组。
• 朋友的名字仅包含字母，长度不超过15个字符，没有重复名字。组标签是0到$M-1$之间的整数。
• 最后一个测试用例后有一行'0 0'表示输入结束。

输出格式

• 每个测试用例输出一行，包含一个整数，表示最大组的最小可能大小。

输入样例 1

3 2
John 0 1
Rose 1
Mary 1
5 4
ACM 1 2 3
ICPC 0 1
Asian 0 2 3
Regional 1 2
ShangHai 0 2
0 0

输出样例 1

2
2

来源

上海2004年相关问题