题目描述

${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 }$需要的最小需要拍摄的照片数量。

样例

输入样例

7 3
1 3
2 4
5 6

输出样例

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}$。