Problem1414--二步侠PIPI

1414: 二步侠PIPI

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 346  Solved: 146
[Submit] [Status] [Web Board] [Creator:]

Description

已知有n个城市,城市之间有m条道路。PIPI准备从1号城市出发,游览剩下所有的城市。但是PIPI有个强迫症,他的行动是二步流的。什么是二步流呢?比如:1号城市和2号城市之间有条道路,2号城市和3号城市之间有条道路,PIPI的路线为1->2->3或者1->2->1。但他只是经过了2号城市到达了3号或1号城市进行游览,而2号城市永远只能经过而无法游览到。
为了满足自己的强迫症,同时又游览所有城市,财大气粗的PIPI可以在任意城市之间修建道路。
出于节约成本低碳环保考虑,PIPI最少修建多少条道路即可游览所有城市?

Input

第一行两个整数n,m,其中:3<=n<=10^5,0<=m<=10^5。
接下来m行,每行两个正整数u,v(u,v<=n),表示u号城市与v号城市之间有一条道路。
PS:数据保证无自环,不保证不会出现重边。

Output

输出PIPI最少需要修建的道路条数。

Sample Input

5 4
1 2
2 3
3 4
4 5

Sample Output

1

Source/Category