6407: 最大化器
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
公司正在准备一个新的分拣硬件，称之为最大化器。
最大化器的$n$个输入都从$1$到$n$，每个输入都代表一个整数。
最大化器有一个输出，代表输入的最大值。最大化器的实现为排序器$(i _1,j _1)$,…,排序器$(i_k,j_k)$的流水线。
每台排序器都有n个输入和n个输出。排序器$(i,j)$对输入$i,i+1,…,j$以非递减顺序输出，对其他输入原样输出。
最后一个排序器的第$n$个输出是最大化器的输出。
经过观察，去掉一些排序器之后，最大化器仍然可以产生正确的结果。
给定排序器序列，求可以产生正确结果的最少排序器数量。
最大化器的$n$个输入都从$1$到$n$，每个输入都代表一个整数。
最大化器有一个输出，代表输入的最大值。最大化器的实现为排序器$(i _1,j _1)$,…,排序器$(i_k,j_k)$的流水线。
每台排序器都有n个输入和n个输出。排序器$(i,j)$对输入$i,i+1,…,j$以非递减顺序输出，对其他输入原样输出。
最后一个排序器的第$n$个输出是最大化器的输出。
经过观察，去掉一些排序器之后，最大化器仍然可以产生正确的结果。
给定排序器序列，求可以产生正确结果的最少排序器数量。
输入
输入的第$1$行包含两个整数$n$和$m（2≤n≤50000，1≤m≤500000）$，分别表示输入的数量和流水线中的排序器数量。
接下来的$m$行描述排序器的初始顺序，第$k$行包含第$k$个排序器的参数，即两个整数$s$和$t（1≤s<t≤n）$，表示排序器排序的范围。
接下来的$m$行描述排序器的初始顺序，第$k$行包含第$k$个排序器的参数，即两个整数$s$和$t（1≤s<t≤n）$，表示排序器排序的范围。
输出
单行输出可以产生正确结果的最少排序器数量。
样例输入 复制
40 6
20 30
1 10
10 20
20 30
15 25
30 40样例输出 复制
4