/ TYWZ / 题库 /

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

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

信息

ID
1002
难度
6
分类
(无)
标签
(无)
递交数
72
已通过
19
通过率
26%
上传者