You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

war

题目背景

$N$个海岛排成一排，共有 $N-1$ 座桥，第 $i$ 座桥连接第 $i$和 $i+1$个海岛。

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

求最小要拆除的桥梁数。

输入格式

第一行输入 $N$ 和 $M$

接下来 $M$ 行，每行输入 $a_i , b_i$ 表示一场战争的对战两方

输出格式

输出一个整数表示答案。

样例

5 2
1 4
2 5

1

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

4

数据范围与提示

• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq a_i < b_i \leq N$
• $(a_i , b_i) 互不相同$