在一个包含 $M$ 条无向道路的网络中有 $N$ 个城镇。每条道路连接一对城镇。政府决定进行一次广度优先搜索（BFS），这意味着要找到 $N$ 个城镇的一个排序，使得如果该排序以 $r$ 开头：

• 除 $r$ 外，每个城镇都与排序中排在它前面的某个城镇相邻。
• 城镇按到 $r$ 的距离非递减的顺序排列。这里，距离是指到达一个城镇所需经过的最少道路数。

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

为了掩盖这个尴尬的错误，政府希望修建新的道路，使得 $1, 2, \dots, N$ 也能成为一个可能的广度优先搜索排序。新道路可以在任意两个城镇之间修建。请问最少需要修建多少条道路？

输入格式

第一行包含两个整数 $N$ 和 $M$ ($1 \le N \le 200\,000, 0 \le M \le \min(200\,000, \frac{N(N-1)}{2})$)。

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

对于 25 分中的 5 分，满足 $N \le 200$。

对于另外 25 分中的 6 分，满足 $N \le 5\,000$。

输出格式

在一行中输出必须修建的最少道路数量。

样例

输入 1

2 0

输出 1

1

说明 1

为了使 $1, 2$ 成为一个广度优先搜索排序，必须在城镇 $1$ 和 $2$ 之间修建一条道路。

输入 2

6 3
1 3
2 6
4 5

输出 2

2

说明 2

通过在 $1$ 和 $2$ 之间以及 $1$ 和 $4$ 之间修建道路，距离序列变为 $0, 1, 1, 1, 2, 2$，这是非递减的。