A22486.照片

省选/NOI-

USACO

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

农夫约翰决定给站在一条线上的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 
    

说明/提示

有 5 头奶牛和 3 张照片。第一张照片包含奶牛 1 到 4 等。

从最后一张照片中,我们知道必须发现 3 号奶牛或 4 号奶牛。通过选择其中任何一张,我们也满足了前两张照片。

首页