题目描述

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

1. 除了 $r$ 之外，每个城镇都与排在它之前的某个城镇相邻。
2. 城镇按到 $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\left(2 \times 10^5, \frac{N(N-1)}{2}\right)$
• $1 \le a_i, b_i \le N$

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

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

---