{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eJamie is a very popular girl and has quite a lot of friends, so she always keeps a very long contact\nlist in her cell phone. The contact list has become so long that it often takes a long time for her to\nbrowse through the whole list to find a friend\u0027s number. As Jamie\u0027s best friend and a programming\ngenius, you suggest that she group the contact list and minimize the size of the largest group, so\nthat it will be easier for her to search for a friends number among the groups. Jamie takes your\nadvice and gives you her entire contact list containing her friends\u0027 names, the number of groups\nshe wishes to have and what groups every friend could belong to. Your task is to write a program\nthat takes the list and organizes it into groups such that each friend appears in only one of those\ngroups and the size of the largest group is minimized.\u003c/p\u003e\n\n\u003cbr\u003e\n\u003cp\u003e\u003cb\u003eInput\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eThere will be at most 20 test cases. Ease case starts with a line containing two integers N and M.\nwhere N is the length of the contact list and M is the number of groups. N lines then follow. Each\nline contains a friend\u0027s name and the groups the friend could belong to. You can assume N is no\nmore than 1000 and M is no more than 500. The names will contain alphabet letters only and will\nbe no longer than 15 characters. No two friends have the same name. The group label is an integer\nbetween 0 and M-1. After the last test case, there is a single line \"0 0\" that terminates the input.\u003c/p\u003e\n\n\u003cbr\u003e\n\u003cp\u003e\u003cb\u003eOutput\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eFor each test case, output a line containing a single integer, the size of the largest contact group.\u003c/p\u003e\n\n\u003cbr\u003e\n\u003cp\u003e\u003cb\u003eSample Input\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\n3 2\u003cbr\u003e\nJohn 0 1\u003cbr\u003e\nRose 1\u003cbr\u003e\nMary 1\u003cbr\u003e\n5 4\u003cbr\u003e\nACM 1 2 3\u003cbr\u003e\nICPC 0 1\u003cbr\u003e\nAsian 0 2 3\u003cbr\u003e\nRegional 1 2\u003cbr\u003e\nShangHai 0 2\u003cbr\u003e\n0 0\u003cbr\u003e\n\u003c/p\u003e\n\n\u003cbr\u003e\n\u003cp\u003e\u003cb\u003eSample Output\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\n2\u003cbr\u003e\n2\u003cbr\u003e\n\u003c/p\u003e\n"}}]}