风雪驿道

题目描述

雪原上共有 $n$ 座驿站，编号为 $1$ 到 $n$。其中一些驿站之间已经修好了双向驿道，因此在同一片连通区域中的驿站可以彼此抵达。

为了让整张驿道网络能够覆盖全部驿站，总务官准备再修建若干条新的双向驿道。每修建一条新驿道，都可以把两片原本分开的连通区域连接起来。

请你求出：至少还要再修多少条驿道，才能让任意两座驿站之间都可以互相到达。

输入格式

第一行包含两个整数 $n, m$。

接下来 $m$ 行，每行包含两个整数 $u, v$，表示驿站 $u$ 和驿站 $v$ 之间已经有一条双向驿道。

输出格式

输出一个整数，表示最少还需要修建的驿道数量。

输入输出样例 #1

输入 #1

6 3
1 2
2 3
5 6

输出 #1

2

输入输出样例 #2

输入 #2

4 3
1 2
2 3
3 4

输出 #2

0

数据范围

对于 $50\%$ 的数据，$1 \le n \le 1000$，$0 \le m \le 5000$。

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$0 \le m \le 2 \times 10^5$，$1 \le u, v \le n$，$u \ne v$。

建议

一刷、二刷、三刷