连通图

题目描述

给定⼀张包含 个结点与 条边的⽆向图，结点依次以 编号，第 条边（ ）连接结点 与结 点 。如果从⼀个结点经过若⼲条边可以到达另⼀个结点，则称这两个结点是连通的。 你需要向图中加⼊若⼲条边，使得图中任意两个结点都是连通的。请你求出最少需要加⼊的边的条数。 注意给出的图中可能包含重边与⾃环。

输入格式

第⼀⾏，两个正整数 ，表⽰图的点数与边数。 接下来 ⾏，每⾏两个正整数 ，表⽰图中⼀条连接结点 与结点 的边。

输出格式

输出⼀⾏，⼀个整数，表⽰使得图中任意两个结点连通所需加⼊的边的最少数量。

样例输入 #1

4 4
1 2
2 3
3 1
1 4

样例输出 #1

0

样例输入 #2

6 4
1 2
2 3
3 1
6 5

样例输出 #2

2

数据范围

对于 % 的测试点，保证 ， 。 对于所有测试点，保证 ， 。

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。