1760: 最大机

Chris Ltd.公司在准备一种称为Maximizer的排序硬件。Maximizer接受n个输入数据，每个输入数据均为整数，Maximizer输出最大的一个值。

Maximizer由一系列依次执行的排序机组成，Sorter(i₁，j₁)…Sorter(i_k，j_k)。每个排序机有n个输入和n个输出。Sorter(i，j)对输入数据中的第i个到第j个整数以非降序排列，而其它数据不变。最后一个排序机的第n个输出就是Maximizer的输出。

有人发现去掉某些排序机后Maximizer的输出仍然正确。给定一系列排序机，找出其中总数最少的一系列排序机对于任意输入都能得到正确结果。

输入文件中的第一行为两个整数n，m（2<=n<=50000，1<=m<=500000）。其中：n如上述，m表示排序机的个数。每个排序机由以下的m行表示。第k行是第k个排序机的参数：i_k，j_k（1<=i_k<j_k<=n）。

输出文件中仅一行为一个整数，即最短的排序机系列的个数。

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

4