D - 岛屿战争

分数: $400$ 分

问题描述

有 $N$ 个岛屿从西到东排列，由 $N-1$ 座桥梁连接。

第 $i$ 座桥梁连接西边的第 $i$ 个岛屿和西边的第 $(i+1)$ 个岛屿。

有一天，一些岛屿之间发生了争端，岛屿居民提出了 $M$ 个请求：

请求 $i$: 发生了位于西边的第 $a_i$ 个岛屿和西边的第 $b_i$ 个岛屿之间的争端。请使这两个岛屿之间的桥梁无法通行。

你决定移除一些桥梁来满足所有这些 $M$ 个请求。

找出必须移除的桥梁的最小数量。

限制

• 所有输入值都是整数。
• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq a_i < b_i \leq N$
• 所有对 $(a_i, b_i)$ 均不相同。

输入

从标准输入获得输入，具体格式如下:

$N$ $M$

$a_1$ $b_1$

$a_2$ $b_2$

$:$

$a_M$ $b_M$

输出

打印必须移除的桥梁的最小数量。

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