洛谷 USACO P2207 Photo

题目描述

Framer Jhon 打算给他的N头奶牛照相，( 2 <= N <= 1 000 000 000) 。

他们排成一条线，并且依次取1~N作为编号。

每一张照片可以拍摄到这列奶牛中一个连续的区间中的奶牛。

对于每一头奶牛，FJ都想要让Ta至少出现在一张照片里。

不幸的是，有K对关系不好的奶牛( 1 <= K <= 1000)，他们拒绝出现在同一张照片里。

已知所有关系不好的奶牛所在的位置，请计算出FJ需要的最小需要拍摄的照片数量。

输入输出格式

输入格式：

*第一行： 两个整数: N,K.

*第2..K+1行中，第i+1行有两个整数，记为A_i与B_i。它们代表着处在队列中第A_i头奶牛与第B_i头奶牛是关系不好的，它们不能出现在同一张照片里。

输出格式：

*一个整数，代表FJ需要的最小需要拍摄的照片数量

输入输出样例

输入样例#1：

7 3

1 3

2 4

5 6

输出样例#1：

3

说明

输出解释：FJ可