题目描述

有一个圆，圆上有 m 个等距离的点，按顺时针依次标号为0,1,......,m-1
圆上有 n 个线段( \(a_i\) , \(b_i\) )( 1<=i<=n ) ( ( \(a_i\) , \(b_i\) )所指的线段是从点 \(a_i\) 顺时针延伸到 \(b_i\) 的线段 )
求最多能选多少个不相交的线段，线段的端点允许重合。

输入数据

第一行有两个数字 m , n
接下来 n 行，第 i+1 行两个数字 \(a_i\)，\(b_i\)，表示第 i 个线段

输出数据

一个数字表示最多能选的线段个数

输入

10 3
0 3
3 7
7 0

输出

3

输入

10 3
0 5
2 7
6 9

输出

2

样例解释：

样例1：选择所有的线段恰好完全覆盖整个圆
样例2：因为线段 1,2 在 (2, 5) 这一段上相交, 所以不能同时选取线段 1,2, 相同地, 线段 2,3 也
不能同时选, 但是线段 1,3 可以同时选择, 所以答案为 2

说明/提示

数据规模与约定
对于 30% 的数据: n <= \(10^3\)
对于 100% 的数据: n <=\(10^5\), m <=\(10^8\), 0 <= \(a_i\), \(b_i\) < m(\(a_i\) != \(b_i\))