题目描述

加布罗沃州由 N 个聚居地组成，为方便起见，编号为 1 到 N。

目前已知有 M 条在大雪之后仍可通行的双向道路连接这些聚居地。

新政府决定优化各聚居地相对于州府加布罗沃的可达性，并要求公布一份按“距离州府远近”排序的名单。该名单应满足：

• 从州府加布罗沃（编号 1）开始；
• 其余聚居地按它们到 1 的最短距离非降序排列；
• 不能从 1 到达的聚居地不应出现在这份名单中，而应被额外列在旁边。

然而，这份名单却很快被写成了：

1, 2, ..., N

后来发现，在制作名单时，本来应当使用广度优先搜索，结果却误用了所谓的宽度优先搜索。于是聚居地实际上是按照“平均宽度”而不是最短距离被排列的。

为了掩盖这一疏忽，政府立刻下令在一些聚居地之间修建新道路，使得排列 1, 2, ..., N 同时也能成为按到州府最短距离非降序排列的结果。

请你编写程序 wfs，求最少需要新建多少条道路，才能使排列 1, 2, ..., N 可以通过给定道路得到，并且也是相对于州府 1 的最短距离非降序排列。

输入格式

第一行输入两个整数 N 和 M，分别表示聚居地数量和当前可通行道路数量。
接下来 M 行，每行输入两个正整数 x, y，表示聚居地 x 与 y 之间有一条可通行的双向道路。

输出格式

输出一个整数，表示最少需要新建的道路条数，使得 1, 2, ..., N 成为按到州府 1 的最短距离非降序排列。

数据范围

• 2 <= N <= 200000
• 0 <= M <= 200000
• 保证任意两个聚居地之间至多有一条可通行道路；
• 不存在连接同一聚居地自身的道路。

子任务

只有当某个子任务及其所依赖的全部子任务全部通过时，才能获得该子任务的分数。

样例

输入

8 5
1 2
2 3
2 4
4 7
5 6

输出

2

说明

图中的红色虚线边表示在某个最优解中需要新建的道路。

初始时，按到州府 1 的最短距离非降序排列的聚居地序列为：

1, 2, 3, 4, 7