题目描述

这个国家有 $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 D2T2