圆(Round 1)

圆(Round 1)

题目描述

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

输入数据

第一行有两个数字 m , n
接下来 n 行,第 i+1 行两个数字 aia_ibib_i,表示第 i 个线段

输出数据

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

输入

10 3
0 3
3 7
7 0

输出

输入

10 3
0 5
2 7
6 9

输出

样例解释:

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

说明/提示

数据规模与约定
对于 30% 的数据: n <= 10310^3
对于 100% 的数据: n <=10510^5, m <=10810^8, 0 <= aia_i, bib_i < m(aia_i != bib_i)

信息

ID
1003
难度
8
分类
(无)
标签
(无)
递交数
25
已通过
3
通过率
12%
被复制
2
上传者