Ujan的抽屉里有很多无用的东西,其中相当一部分是他的数学笔记本:是时候整理它们了。这次他发现了一本布满灰尘的旧图论笔记本,上面有图的描述。
这是 $$$n$$$ 个顶点上的无向加权图。它是一个完整的图:每对顶点都由一条边连接。每条边的权重要么是$$$0$$$,要么是$$$1$$$;恰好 $$$m$$$ 边的权重为 $$$1$$$,所有其他边的权重为 $$$0$$$。
由于 Ujan 并不想整理他的笔记,他决定找到图的最小生成树的权重。 (生成树的权重是其所有边的总和。)你能为 Ujan 找到答案,让他停止拖延吗?
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$0 \leq m \leq \min(\frac{n(n-1)}{2},10^5)$$$),权重 $$$1$$$ 中的顶点数和边数图表。
接下来的 $$$m$$$ 行的第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$),权重第 $$$i$$$ 边的端点$$$1$$$。
确保输入中没有边缘出现两次。
输出
输出一个整数,即图的最小生成树的权重。
示例
输入 #1
6 11 1 3 1 4 1 5 1 6 2 3 2 4 2 5 2 6 3 4 3 5 3 6
输出 #1
2
输入 #2
3 0
输出 #2
0
注意
第一个示例的图表如下所示。虚线边的权重为 $$$0$$$,其他边的权重为 $$$1$$$。其中一棵最小生成树以橙色突出显示,总重量为 $$$2$$$。
在第二个示例中,所有边的权重为 $$$0$$$,因此任何生成树的总权重为 $$$0$$$。