题目描述

探索火星洞穴系统本来是一项在地球上提前规划好的简单工作。

一个洞穴系统中包含若干彼此不连通的洞室。由于这些洞室无法直接从地表进入，你获得了一台钻掘设备，可以在某些洞室之间挖掘通道。

土壤并不均匀，运行钻掘设备会消耗大量柴油。为了节省柴油，你需要挖出尽可能少的通道，使每个洞室都能够从地表通过已挖通道到达。

同时，最终系统还应满足：从地表到任意洞室需要经过的通道数量尽可能少。

扫描结果给出了：

• 每个洞室的危险等级；
• 哪些洞室对之间可以挖通道；
• 哪些洞室可以直接与地表挖通道。

假设所有可能的通道都已经挖好。定义一个洞室的距离为从地表到达它最少需要经过的通道数量。

由于安全规定，挖掘过程必须遵守以下优先级：

1. 在任何更远的洞室之前，必须先让距离更近的洞室可达；
2. 如果有多个同距离洞室可以作为下一个目标，则选择危险等级最低的洞室；
3. 如果目标洞室已经确定，但仍有多条可挖通道可以把它接入当前系统，则选择危险等级最低的已可达起点。

洞室编号已经按照危险等级从低到高排列，因此编号越小，危险等级越低。

按照上述顺序发现洞室，会使你多次沿已挖通道移动钻掘设备。

移动钻掘设备也会消耗柴油，虽然远少于真正挖掘通道。你想知道整个工程中总共需要经过多少次通道。

开始时设备位于地表节点 $0$。统计一直持续到所有需要的通道都挖完。

输入格式

第一行包含两个整数 $N,M$：

$N$ 表示洞室节点数量，其中包括地表。

• 地表编号为 $0$；
• 其他洞室编号为 $1,2,\ldots,N-1$；
• 编号按照危险等级递增排列。

接下来 $M$ 行，每行包含两个整数，表示对应的两个洞室之间，或某个洞室与地表之间，存在可以挖通道的松软土层。

输出格式

输出一个整数，表示按照规定完成整个洞穴系统后，钻掘设备总共经过的通道次数。

样例 1

输入

5 5
0 1
1 2
2 3
3 4
4 0

输出

10

样例 2

输入

5 4
0 1
1 2
2 3
3 4

输出

4

样例 3

输入

5 6
0 1
0 2
0 3
0 4
1 4
2 3

输出

7