#P2207. Photo
Photo
题目描述
Farmer John 打算给他的 头奶牛照相。
他们排成一条线,并且依次取 作为编号。
每一张照片可以拍摄到这列奶牛中一个连续的区间中的奶牛。
对于每一头奶牛,FJ 都想要让 Ta 至少出现在一张照片里。
不幸的是,有 对关系不好的奶牛,他们拒绝出现在同一张照片里。
已知所有关系不好的奶牛所在的位置,请计算出 FJ 需要的最小需要拍摄的照片数量。
输入格式
第一行:两个整数:,。
第 行中,第 行有两个整数,记为 与 。它们代表着处在队列中第 头奶牛与第 头奶牛是关系不好的,它们不能出现在同一张照片里。
输出格式
一个整数,代表 FJ 需要的最小需要拍摄的照片数量。
7 3
1 3
2 4
5 6
3
提示
样例输入输出 1 解释
FJ 可以只拍三张照片:,,。
数据规模与约定
对于 的数据,保证 ,,。