#2422. 道路建设

道路建设

Description

热带岛屿负责道路的人们想修理和升级岛上各个旅游景点之间的道路。

道路本身也很有趣,它们从不在交叉路口汇合,而是通过桥梁和隧道相互交叉或相互通过。通过这种方式,每条道路都在两个特定的旅游景点之间运行,这样游客就不会迷失。

不幸的是,当建筑公司在特定道路上工作时,该道路在任何一个方向都无法使用。如果在两个旅游景点之间无法同行,则即使建筑公司在任何特定时间只在一条道路上工作,也可能出现问题。

道路部门已经决定在景点之间建造新的道路,以便在最终配置中,如果任何一条道路正在建设,则仍然可以使用剩余的道路在任意两个旅游景点之间旅行。我们的任务是找到所需的最少数量的新道路。

image

Format

Input

输入的第1行将包括正整数n3n1000n (3≤n ≤1000)r2r1000r (2≤r≤1000),其中n 是旅游景点的数量,rr 是道路的数量。旅游景点的编号为1n1~n

以下rr 行中的每一行都将由两个整数vv ww 组成,表示在vv和w 的景点之间存在道路。请注意,道路是双向的,在任何两个旅游景点之间最多有一条道路。

此外,在目前的配置中,可以在任意两个旅游景点之间旅行。

Output

单行输出需要添加的最少道路数量。

Samples

10 12
1 2
1 3
1 4
2 5
2 6
5 6
3 7
3 8
7 8
4 9
4 10
9 10
3 3
1 2
2 3
1 3
2
0

来源

POJ3352