该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

求最小要拆除的桥梁数。

输入格式

第一行两个正整数 $N, M$，$2 \le N \le 10^5$，$1 \le M \le 10^5$。

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

输出格式

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

5 2
1 4
2 5

1

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

2

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

4