岛屿之争

题目描述

东西方向一字排开有 $N$ 个岛屿和 $N-1$ 座桥。

第 $i$ 座桥连接从西数第 $i$ 个岛屿和从西数第 $i+1$ 个岛屿。

某天,一些岛屿之间发生了争端,岛民们提出了 $M$ 个要求。

要求 $i$:由于从西数第 $a_i$ 个岛屿和从西数第 $b_i$ 个岛屿之间发生了争端,希望这些岛屿之间无法通过若干座桥往返。

你决定拆除一些桥来满足全部 $M$ 个要求。

求需要拆除的桥的最少数量。

输入格式

输入从标准输入以以下格式给出。

$N$ $M$

$a_1$ $b_1$

$a_2$ $b_2$

$:$

$a_M$ $b_M$

输出格式

输出需要拆除的桥的最少数量。

样例

5 2
1 4
2 5

1

拆除连接从西数第 $2$ 个岛屿和第 $3$ 个岛屿的桥即可实现。

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

数据范围

• 输入均为整数
• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq a_i \lt b_i \leq N$
• 所有数对 $(a_i, b_i)$ 各不相同