题目描述

给定一个长度为n的大区间，区间范围为1~n。再给出m个小区间两侧的端点坐标，求最少使用多少个小区间可以将整个大区间完全覆盖。完全覆盖指的是1~3和(3~5或2~5)的小区间可以完全覆盖1~5的大区间,但1~3和4~5的小区间不可以完全覆盖1~5的大区间。

输入格式

第一行输入大区间的长度n和小区间总的个数m，（1≤n≤1e6，1≤m≤1e5） 第2到m+1行，每行输入两个范围在1~n之间的整数，分别代表小区间的两个端点坐标。

输出格式

若可以完全覆盖，则求出最少需要多少个小区间可以完全覆盖大区间，反之不可完全覆盖的话，输出-1。

7 4
1 3
2 5
4 7
5 7

3