Photo

题目描述

Farmer John 打算给他的 $n$ 头奶牛照相。 他们排成一条线,并且依次取 $1\sim n$ 作为编号。 每一张照片可以拍摄到这列奶牛中一个连续的区间中的奶牛。 对于每一头奶牛,FJ 都想要让 Ta 至少出现在一张照片里。 不幸的是,有 $k$ 对关系不好的奶牛,他们拒绝出现在同一张照片里。 已知所有关系不好的奶牛所在的位置,请计算出 FJ 需要的最小需要拍摄的照片数量。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

7 3
1 3
2 4
5 6

输出样例 #1

3

说明

#### 样例输入输出 1 解释 FJ 可以只拍三张照片:$[1,2]$,$[3,5]$,$[6,7]$。 --- #### 数据规模与约定 对于 $100\%$ 的数据,保证 $2\le n\le10^9$,$1\le k\le1000$,$1 \leq a_i, b_i \leq n$。