排序网络

时间限制:10s      空间限制:256MB

题目描述

最近HH公司推出了新型的排序网络。简单的来说,这种排序网络是由一系列的的排序器按顺序组成。某个排序器可以将排序网络[L,R]间的输入端进行排序。经过排序器处理[L,R]之间排成非递减顺序。不同排序器LR值不同。
虽然排序网络很有用,但是很多情况下面我们可能只要排序网络中的最大值,所以Henryy公司决定利用已有的排序网络再开发一个只求最大值的网络。改造方法很简单,只需要隐蔽原有网络中的某些排序器,使得最后一个输入端的值是最大值。这样一来既可以减少开发成本,又可以降低网络的功耗。
现在的任务是,给N个不同的排序器,要求你改造这个网络,使得网络最后一个输入端经过操作后是这个网络的最大值。要求使用的排序器要尽可能少。(也就是说,不能改变原来排序网络的结构,你可以选择某个排序器是否隐蔽)


输入格式

 
第一行是两个数NMN表示排序网络有N个输入端。接下来将会有M行,每行2个数LiRi,分别表示排序器I排序的范围[LiRi]。(,1<=Li<=Ri<=N
 


输出格式

 
     输出一个数P,表示使用的最少排序器。-1表示无解(由于设计缺陷)。
 


样例输入

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

样例输出

4
【数据约定】
0≤N≤50000,0≤M≤500000。

提示

没有写明提示


题目来源

没有写明来源