← 返回题目
题库练习 照片
← 上一题 下一题 →

A2775 | 照片

来源USACO / 2013
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

农夫约翰决定给站在一条线上的N(1 <= N <= 200,000)头奶牛制作一张全家福照片，N头奶牛编号1到N。


于是约翰拍摄了M(1 <= M <= 100,000)张照片，每张照片都覆盖了连续一段奶牛：第i张照片中包含了编号a\_i 到 b\_i的奶牛。但是这些照片不一定把每一只奶牛都拍了进去。


在拍完照片后，约翰发现了一个有趣的事情：每张照片中都**有且仅有**一只身上带有斑点的奶牛。约翰意识到他的牛群中有一些斑点奶牛，但他从来没有统计过它们的数量。 根据照片，请你帮约翰估算在他的牛群中最多可能有多少只斑点奶牛。如果无解，输出“-1”。

输入格式

* 第 1 行：两个整数 N 和 M。

* 第 2..M+1 行：第 i+1 行包含 a_i 和 b_i。

输出格式

* 第 1 行：FJ 农场中最大可能的斑点奶牛数量，如果没有可能的解决方案，则为 -1。

输入输出样例

输入 #1
5 3 
1 4 
2 5 
3 4
输出 #1
1
C++ 编辑器
输入
输出