[CCO2021] Bread First Search

这个国家有 $n$ 个城市和 $m$ 条双向道路。 有一个人要游览这个国家，但他很讲究。他要求游览线路必须是一个 BFS（Bread First Search，面包优先搜索）序，必须访问每个城市各一次，且满足以下条件： - 首个城市可以任选； - 除了首个城市外，每个城市被访问前至少有一个相邻城市已经被访问过； - 每个城市与首个城市的距离单调不降。其中两个城市的距离定义为它们路径边数的最小值。 这个人还有强迫症，一定要按照编号 $1 \sim n$ 的顺序将每个城市访问一次。为了使这条游览线路符合上述所有要求，政府需要新修若干条道路。请问最少需要新修多少条道路？

第一行，两个整数 $n, m$； 接下来 $m$ 行，每行两个整数 $a, b$，表示这个国家的一条双向道路。

一行，一个整数，表示所求的值。

2 0

1

6 3
1 3
2 6
4 5

2

#### 样例 #2 解释 一种符合要求的方式是，在城市 $1, 2$ 之间修一条路，在城市 $1, 4$ 之间修一条路。此时城市 $1$ 与城市 $1 \sim 6$ 的距离分别是 $0, 1, 1, 1, 2, 2$。 #### 数据范围 对于 $\frac{11}{32}$ 的数据，$1 \leq n \leq 200$； 对于 $\frac{5}{8}$ 的数据，$1 \leq n \leq 5 \times 10^3$； 对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^5$，$0 \leq m \leq \min(2 \times 10^5, \frac{n(n - 1)}{2})$，$1 \leq a, b \leq n$，**保证没有重边和自环**。 #### 题目来源 [CCO2021](https://cemc.math.uwaterloo.ca/contests/computing/2021/index.html) D2T2