A2775. 照片
编程题
省选/NOI-
知识点
题目描述
农夫约翰决定给站在一条线上的N(1 <= N <= 200,000)头奶牛制作一张全家福照片，N头奶牛编号1到N。
于是约翰拍摄了M(1 <= M <= 100,000)张照片，每张照片都覆盖了连续一段奶牛：第i张照片中包含了编号a\_i 到 b\_i的奶牛。但是这些照片不一定把每一只奶牛都拍了进去。
在拍完照片后，约翰发现了一个有趣的事情：每张照片中都**有且仅有**一只身上带有斑点的奶牛。约翰意识到他的牛群中有一些斑点奶牛，但他从来没有统计过它们的数量。 根据照片，请你帮约翰估算在他的牛群中最多可能有多少只斑点奶牛。如果无解，输出“-1”。
于是约翰拍摄了M(1 <= M <= 100,000)张照片，每张照片都覆盖了连续一段奶牛：第i张照片中包含了编号a\_i 到 b\_i的奶牛。但是这些照片不一定把每一只奶牛都拍了进去。
在拍完照片后，约翰发现了一个有趣的事情：每张照片中都**有且仅有**一只身上带有斑点的奶牛。约翰意识到他的牛群中有一些斑点奶牛，但他从来没有统计过它们的数量。 根据照片，请你帮约翰估算在他的牛群中最多可能有多少只斑点奶牛。如果无解，输出“-1”。
输入格式
* 第 1 行：两个整数 N 和 M。
* 第 2..M+1 行：第 i+1 行包含 a_i 和 b_i。
* 第 2..M+1 行：第 i+1 行包含 a_i 和 b_i。
输出格式
* 第 1 行：FJ 农场中最大可能的斑点奶牛数量，如果没有可能的解决方案，则为 -1。
输入输出样例
输入 #1
5 3 1 4 2 5 3 4
输出 #1
1
说明/提示
有 5 头奶牛和 3 张照片。第一张照片包含奶牛 1 到 4 等。
从最后一张照片中，我们知道必须发现 3 号奶牛或 4 号奶牛。通过选择其中任何一张，我们也满足了前两张照片。
从最后一张照片中，我们知道必须发现 3 号奶牛或 4 号奶牛。通过选择其中任何一张，我们也满足了前两张照片。