题目描述

有 $n$ 个城市，编号从 1 到 $n$。现在已经修好了 $m$ 条道路，一条道路可以连接第 $x$ 个和第 $y$ 个城市。

现在询问最少再修几条道路，可以使得所有城市都连通（可以通过道路从任意一个城市到另一个城市）。

输入格式

第一行两个整数 $n,m$，代表城市数量和已修道路数。

接下来 $m$ 行，每行有两个整数 $x,y(x≠y)$，表示一条从 $x$ 城市到 $y$ 城市的路。

输出格式

输出一个数表示答案。

5 4
1 2
2 3
1 3
4 5

1

数据规模

对于所有数据，保证 $1≤n,m≤100000, 1≤x,y≤n，x≠y$。

提示

本题数据较大，可能导致很深的递归深度，后台已经设置较大的栈空间。但也请自行尝试创建进程，开设足够大的栈空间。