#SYUCT13C. 月光小径
月光小径
题目描述
永夜异变之后,月亮被换成了假的,迷途竹林的夜晚格外昏暗。为了前往永远亭查明真相,博丽灵梦需要沿着一条由 个首尾相接的单位路段组成的小径前进。
这些单位路段依次编号为
小径旁恰好有 盏竹灯。点亮第 盏竹灯后,它会照亮编号在闭区间
内的所有单位路段,包括编号为 和 的路段。
灵梦想知道:最少点亮几盏竹灯,才能让编号为 的每个单位路段都被至少一盏灯照亮?
如果无论如何都无法照亮整条小径,请输出 。
输入格式
第一行输入两个整数 和 (,),分别表示竹灯数量和单位路段数量。
接下来 行,每行输入两个整数 和 (),表示第 盏竹灯能够照亮编号从 到 的所有单位路段。
输出格式
输出一行一个整数:
- 如果能够照亮整条小径,输出最少需要点亮的竹灯数量;
- 否则输出 。
样例
3 10
1 6
2 3
5 10
2
提示
样例中,点亮第 盏竹灯(照亮编号 至 的路段)和第 盏竹灯(照亮编号 至 的路段),即可照亮全部 个单位路段,因此最少需要点亮 盏。
例如,一盏灯照亮编号 至 的路段,另一盏灯照亮编号 至 的路段时,两者合计恰好照亮编号 至 的所有单位路段,中间没有遗漏。