← 返回题目列表

Codeforces · 1242/B

B. 0-1最小生成树

中文机器翻译题面 查看原题

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$$$。