题目描述

There are $N$ islands lining up from west to east, connected by $N-1$ bridges.

The $i$-th bridge connects the $i$-th island from the west and the $(i+1)$-th island from the west.

One day, disputes took place between some islands, and there were $M$ requests from the inhabitants of the islands:

Request $i$: A dispute took place between the $a_i$-th island from the west and the $b_i$-th island from the west. Please make traveling between these islands with bridges impossible.

You decided to remove some bridges to meet all these $M$ requests.

Find the minimum number of bridges that must be removed.

有 $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$

输出格式

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

样例 #1

样例输入 #1

5 2
1 4
2 5

样例输出 #1

1

样例 #2

样例输入 #2

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

样例输出 #2

2

样例 #3

样例输入 #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 \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq a_i \lt b_i \leq N$
• 所有成对的 $(a_i, b_i)$ 都是不同的。

样例 $1$ 解释

从西面拆除连接第二岛和第三岛的桥梁，即可满足要求。