UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2841. [Cerc2005] Knights of the Round Table

统计 下载数据

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

2

Hint

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

Source