#P2207. Photo

Photo

题目描述

Farmer John 打算给他的 nn 头奶牛照相。

他们排成一条线,并且依次取 1n1\sim n 作为编号。

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

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

不幸的是,有 kk 对关系不好的奶牛,他们拒绝出现在同一张照片里。

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

输入格式

第一行:两个整数:nnkk

2k+12\ldots k+1 行中,第 i+1i+1 行有两个整数,记为 aia_ibib_i。它们代表着处在队列中第 aia_i 头奶牛与第 bib_i 头奶牛是关系不好的,它们不能出现在同一张照片里。

输出格式

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

7 3
1 3
2 4
5 6
3

提示

样例输入输出 1 解释

FJ 可以只拍三张照片:[1,2][1,2][3,5][3,5][6,7][6,7]


数据规模与约定

对于 100%100\% 的数据,保证 2n1092\le n\le10^91k10001\le k\le10001ai,bin1 \leq a_i, b_i \leq n