题目描述

$\red{Farmer John }$打算给他的 $\red{n }$头奶牛照相。

他们排成一条线，并且依次取 $\red{1\sim n}$作为编号。

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

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

不幸的是，有 $\red{k }$对关系不好的奶牛，他们拒绝出现在同一张照片里。

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

输入格式

第一行：两个整数:$\red{n，}$$\red{k}$。

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

输出格式

一个整数，代表 $\red{FJ }$需要的最小需要拍摄的照片数量。

样例

输入样例

7 3
1 3
2 4
5 6

输出样例

3

提示

样例输入输出 $\red{1 }$解释 $\red{FJ }$可以只拍三张照片：$\red{[1,2]，}$$\red{[3,5]，}$$\red{[6,7]}$。

数据规模与约定 对于 $\red{100\% }$的数据，保证 $\red{2\le n\le10^9，}$$\red{1\le k\le1000，}$$\red{1 \leq a_i, b_i \leq n}$。