Description

公司正在准备一个新的分拣硬件，称之为最大化器。最大化器的$n$个输入都从$1$到$n$，每个输入都代表一个整数。最大化器有一个输出，代表输入的最大值。最大化器的实现为排序器$(i _1,j _1)$,…,排序器$(i_k,j_k)$的流水线。每台排序器都有n个输入和n个输出。排序器$(i,j)$对输入$i,i+1,…,j$以非递减顺序输出，对其他输入原样输出。最后一个排序器的第$n$个输出是最大化器的输出。经过观察，去掉一些排序器之后，最大化器仍然可以产生正确的结果。给定排序器序列，求可以产生正确结果的最少排序器数量。

Format

Input

输入的第$1$行包含两个整数$n$和$m（2≤n≤50000，1≤m≤500000）$，分别表示输入的数量和流水线中的排序器数量。接下来的$m$行描述排序器的初始顺序，第$k$行包含第$k$个排序器的参数，即两个整数$s$和$t（1≤s<t≤n）$，表示排序器排序的范围。

Output

单行输出可以产生正确结果的最少排序器数量。

Samples

40 6
20 30
1 10
10 20
20 30
15 25
30 40

4

来源

POJ1769