问题描述

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

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

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

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

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

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

输入

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

$N\ M$

$a_1\ b_1$

$a_1\ b_1$

.

.

.

$a_M\ b_M$

输出

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

5 2
1 4
2 5

1

5 2
1 4
2 5

2

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

4

提示

【样例解释1】

通过移除连接西边的第二个和第三个岛屿的桥梁，可以满足所有的请求。

所有输入的值都是整数

$2 \leq N \leq 10^5$

$1 \leq M \leq 10^5$

$1 \leq a_i < b_i \leq N$

所有的$(a_i,b_i)$均不相同