问题 D: 传送机(sent.*)

问题 D: 传送机(sent.*)

时间限制: 1 Sec  内存限制: 128 MB
提交: 32  解决: 3
[提交] [状态] [讨论版] [命题人:]

题目描述

黄黄同学要到清华大学上学去了。
黄黄同学很喜欢清华大学的校园,每次去上课时总喜欢把校园里面的每条路
都走一遍,当然,黄黄同学想每条路也只走一遍。我们一般人很可能对一些地图
是办不到每条路走一遍且仅走一遍的,但是黄黄同学有个传送机,他可以任意地
将一个人从一个路口传送到任意一个路口。
可是,每传送一次是需要耗费巨大的内力的,黄黄同学希望可以用最少的传
送次数完成游遍校园,你能帮助他吗?
因为黄黄同学只是游历校园,于是我们可以认为黄黄同学可以从任意点开始,
到任意点结束。
注意:不必经过所有的点。

输入

输入第一行一个整数 N,表示黄黄的校园里一共有多少路口。
第二行一个整数 M,表示路口之间有 M 条路。
后面 M 行,每行两个整数 a、b,表示 a 与 b 之间有一条路,且路是双向的。

输出

输出一行一个整数 S,表示黄黄同学最少的传送次数。

样例输入

3
2
1 2
2 3

样例输出

0

提示

数据规模:
对于 100%的数据满足:N<=100000,M<=500000,1<=a,b<=N。
样例二
输入
5
4
1 2
2 3
2 4
2 5
输出
1

[提交][状态]