[AdditionalFile3581.zip](file://AdditionalFile3581.zip?type=additional_file)

#3581. 「CCO 2021」面包优先搜索

标签: 传统 | 时间限制: 1000 ms | 内存限制: 1024 MiB |

题目描述

译自 CCO 2021 Day2「Bread First Search」

有一个由 $N$ 个城镇和 $M$ 条无向道路形成的路网。每条路连接一对城镇。政府决定进行一次宽度优先搜索（breadth first search），这意味着找到 $N$ 个城镇的一个顺序，如果这个排序以 $r$ 开始，满足：

• 除了 $r$ 之外，每个城镇都与排在它之前的某个城镇相邻。
• 城镇按到 $r$ 的距离单调不降的顺序给出。这里，距离是指到一个城镇所最少要经过的道路条数。

然而，某个人错误地进行了一次面包（bread）优先搜索。他们找到的排序是 $1,2,3,\ldots ,N$（这个排序是通过按面包产量递增的顺序对城镇排序得到的）。

为了掩饰这个尴尬，政府想要修建一些新的道路，使得 $1,2,\ldots,N$ 也是一个可能的宽度优先搜索排序。新的道路可以在任意两个城市之间新建。请问最少要修建多少条道路？

输入格式

第一行包含两个整数 $N$ 和 $M$。

接下来 $M$ 行，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$，表示第 $i$ 条路的两端。保证 $a_i\neq b_i$，并且任意两个城镇之间最多只有一条路。

输出格式

输出一行一个整数，表示最少要修建多少条道路。

样例 1

输入

2 0

输出

1

对于要让 $1,2$ 成为一个宽度优先搜索的排序，就必须修建一条城镇 $1$ 和 $2$ 之间的路。

样例 2

输入

6 3
1 3
2 6
4 5

输出

2

在城镇 $1$ 和 $2$，城镇 $1$ 和 $4$ 之间修路，距离数列就会变为 $0,1,1,1,2,2$，是非降的。

数据范围与提示

对于全部数据，$1\le N\le 2\times 10^5,0\le M\le \min(2\times 10^5,\frac{N(N-1)}{2}),1\le a_i,b_i\le N$。

对于 $20\%$ 的分数，$N\le 200$。

对于另外 $24\%$ 的分数，$N\le 5000$。