Description

K国正在进攻J国，K国的部队集结在一条铁路线上的N个点上。

这N个点，每个点均只与其后面的那个点相连。

现在J国想精确打击，希望这N个点中有M对点是不连通的

现希望求出至少断开几条边，达到目标。

Format

Input

第一行给出N，M

接下来M行，描述J国的战略意图

N，M<=1e5

Output

如题

Samples

5 2
1 4
2 5

1

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

2

Hint

对于样例1

断开第2个点与第3个点之间的边即可

对于样例2

断开4与5之间的边以及8与9之间的边