{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"亚瑟王要在圆桌上召开骑士会议,为了不引发骑士之间的冲突,并且能够让会议的议题有令人满意的结果,每次开会前都必须对出席会议的骑士有如下要求:\n\n1、 相互憎恨的两个骑士不能坐在直接相邻的2个位置;\n\n2、 出席会议的骑士数必须是奇数,这是为了让投票表决议题时都能有结果。\n\n \n\n如果出现有某些骑士无法出席所有会议(例如这个骑士憎恨所有的其他骑士),则亚瑟王为了世界和平会强制把他剔除出骑士团。\n\n 现在给定准备去开会的骑士数n,再给出m对憎恨对(表示某2个骑士之间使互相憎恨的),问亚瑟王至少要剔除多少个骑士才能顺利召开会议?\n"}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n The input contains several blocks of test cases. Each case begins with a line containing two integers 1 ≤ n ≤ 1000 and 1 ≤ m ≤ 1000000 . The number n is the number of knights. The next m lines describe which knight hates which knight. Each of these m lines contains two integers k1 and k2 , which means that knight number k1 and knight number k2 hate each other (the numbers k1 and k2 are between 1 and n ). \n \u003cbr\u003e \n \u003cbr\u003eThe input is terminated by a block with n \u003d m \u003d 0 . \n \u003cbr\u003e \n \u003cbr\u003e\n \u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n For each test case you have to output a single integer on a separate line: the number of knights that have to be expelled. \n \u003cbr\u003e \n \u003cbr\u003e\n \u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e5 5\n1 4\n1 5\n2 5\n3 4\n4 5\n0 0\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e2\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n Huge input file, \u0027scanf\u0027 recommended to avoid TLE. \n \u003cbr\u003e\n \u003c/div\u003e"}}]}