Description

WSW是一个投资家，他来到了喵哈大联盟物色投资目标，喵哈大联盟由n个城市组成，在这n个城市之间有很多条道路，WSW认为交通状况是衡量一个城市是不是具有投资潜力的重要标志，因为他是一个投资家，所以他想知道在这n个城市至少修建多少条道路才能使城市之间两两连通。（可能存在重边）

Format

Input

第一行输入三个整数n,m分别代表城市的数量，道路的数量。
接下来m行每行有两个数a,b，代表城市a和城市b之间存在一条道路。

Output

输出至少修建的道路的数量。

Sample 1

Input

5 4
1 2
2 3
3 4
4 1

Output

1
【样例解释】
需要在5和1（2，3，4）之间修一条路使之连通。

Limitation

1s, 131072KiB for each test case.

Hint

对于30%的数据满足：n,m<=100
对于60%的数据满足： n,m<=10000;
对于100%的数据满足： n,m<=100000;

Source

高一年级信息学奥赛模拟考(一)（第二学期）