6841: BZOJ2841：[Cerc2005] Knights of the Round Table

蹭饭骑士是一个非常吸引人的职业：寻找圣杯，把妹，以及和同事一起蹭饭，都是很有意思的事。因此，在最近几 年里，亚瑟王史无前例的扩招蹭饭骑士，并不令人惊讶。现在这里有许多蹭饭骑士，每个蹭饭骑士都收到一份珍贵 的邀请函，被邀请去英灵殿蹭饭。这些骑士将要环绕着坐在一个圆桌旁，但通常只有一小部分骑士会来，因为剩下 的骑士正忙着在全国各地为人民服务。不幸的是，这些蹭饭骑士的酒量不行，很容易喝高。当他们喝高时，一些不 幸的便当事件将会发生。因此，亚瑟王请来了长门大神，来确保在未来不会有类似的事情发生。在仔细分析了这个 问题后，长门大神意识到要想避免骑士之间相互斗殴，当且仅当他们在圆桌旁所坐的位置，符合以下条件： 1. 某些骑士之间有仇，避免相互之间有仇的骑士挨在一块。 2. 当场上有偶数个骑士时，若通过投票解决问题的话，正方与反方的票数可能相同，这会令骑士们非常不爽。因此 ，只能有奇数个骑士坐在圆桌旁。长门大神会尽量的满足以上两个条件，否则她会代替亚瑟王宣布散会（若只有一个 骑士在场的话，也会宣布散会，因为一个骑士不管怎么坐，都不可能环绕一个圆桌）。这将意味着无论如何安排，一 些骑士都无法到场，无法坐在圆桌旁边（其中一种情况即为当这个骑士对所有骑士都有仇时，当然还可能是其他情况）。 若一个蹭饭骑士永远无法到场，则这个骑士就失去了“蹭饭”的意义，他将会被开除。这些骑士将会被降级，降到诸如 “爱的战士”“蘑菇骑士”“人鱼骑士”之类的职阶。为了帮助长门大神，你必须写一个程序来计算会有多少蹭饭骑士 会被开除。

输入格式

第一行两个整数，N和M，N为骑士的数量。 接下来M行每行两个整数i,j，表示i与j之间没有仇恨。输入数据保证不会有重边和自环。

输出格式

一个整数，为所求的答案。

样例输入

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

样例输出

2

提示

1<=N<=100000 0<=M<=300000

题目来源