SP3930 MPART - Group Partition

Jamie 是一个非常受欢迎的女孩，她有很多朋友，因此手机里存储了很长的联系人列表。由于联系人列表太长，她经常需要花费大量时间来查找某个朋友的电话号码。 作为 Jamie 最好的朋友和编程天才的你，建议她将联系人列表进行分组，并尽量减小最大一组的成员数量，这样查找起来会更方便。Jamie 采纳了你的建议，并提供了她的整个联系人名单，包括朋友的名字、希望分成的组数，以及每个朋友可以归属的组。 你的任务是编写一个程序，将联系人名单合理地分组，让每个朋友只出现在一个组里，并且使得最大组的大小最小。

最多会有 20 组测试数据。每组数据开始于一行包含两个整数 $N$ 和 $M$，其中 $N$ 表示联系人名单的长度，$M$ 是组的数量。 接下来的 $N$ 行中，每行包含一个朋友的名字及该朋友所属的可能组。假定 $N$ 不超过 1000，$M$ 不超过 500。名字由字母组成，长度不超过 15 个字符。所有名字互不相同。组标签是介于 $0$ 到 $M-1$ 之间的整数。 当所有测试数据结束时，会有一行 `0 0`，表示输入终止。 **示例输入** ``` 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 ```

对于每组测试数据，输出一个整数，表示最大联系人组的大小。 **示例输出** ``` 2 2 ``` **注意：可能有大量数据输入**

- $1 \leq N \leq 1000$ - $1 \leq M \leq 500$ **本翻译由 AI 自动生成**