Problem G
Win Diesel

Exploring cave systems on Mars is an easy procedure which was pre-planned on Earth. Each cave system contains several cave rooms which are pairwise disconnected. As the cave rooms are not accessible from the surface, you were given a digging rig so that you are able to dig channels between some of them.

The soil is not uniform and running the digging rig is extremely diesel intensive. To save diesel you need to excavate the minimum number of channels so that every cave is accessible from the surface through the channels. At the same time, the resulting system should be connected in a way so that the number of channels you need to pass to get from the surface to any particular cave is minimized.

You ran a scan over the whole cave system and now you know the danger level of each cave room. The scan also shows which pairs of cave rooms, or which cave room and surface, are separated by soil that can be dug through to create a channel. Let the distance of a cave room be the minimum possible number of channels that need to be traversed to reach the room from the surface, if all the possible channels were dug.

Due to safety reasons, the procedure prescribes that in the process of digging, the closest (least distant) cave rooms must be made accessible before any more distant cave rooms are made accessible. If this is not uniquely determining the next room to be made accessible, then the safest (least dangerous) room should be chosen from the candidates. If this does not uniquely determine the channel that needs to be dug, then out of already accessible starting locations the safest one has to be chosen.

Discovering the rooms in the given order forces you to traverse through the dug channels multiple times. The machine you use to move the digging rig also drinks diesel, although much less than the digging rig. You wonder, what is the amount of diesel that you will need to do this job – this is proportional to the number of channels that will need to be traversed, starting from $0$ and counting until all the channels are dug.

Input

The first line contains two integers $N$ and $M$ ($1 \le N \le 2 \cdot 10^5$, $0 \le M \le 2 \cdot 10^5$) the number of cave rooms (including surface) and the number of possible cave channels, respectively.

Surface is denoted by $0$ and the cave rooms are denoted by integers from $1$ to $N - 1$ and are ordered by increasing danger level.

Each of the next $M$ lines contains two integers, representing two cave rooms or a cave room and surface, which are separated by soil soft enough so that it can be dug through to create a connecting channel.

Output

Print a single integer – the total number of channel traversals you need to perform to make the whole cave system accessible according to the prescribed procedure.

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

10

5 4
0 1
1 2
2 3
3 4

4

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

7