当前没有测试数据。

描述

$N$ 个部落排成一列，相邻两个部落之间都有一座桥当做连接。

一天这些部落之间发生了 $M$ 场战争，第 $i$ 场是 $A$i$​$ 和 $B$i$​$ ，现在要求拆除一些桥梁使得任意两个发生了战争的部落都不可以到达彼此。

求最小要拆除的桥梁数。

输入

第一行两个正整数 $N$,$M$。

接下来 $M$ 行，每行两个正整数 $a$,$b$，表示 $a$ 和 $b$ 之间有一场战争。

输出

需要拆除的桥梁的最小数目。

输入样例 1

5 2
1 4
2 5

输出样例 1

1

输入样例 2

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

输出样例 2

2

输入样例 3

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

输出样例 3

4

提示

$2\leq N \leq10^5$ $1\leq M \leq10^5$