题目描述

Farmer John 打算给他的 $n$ 头奶牛照相。他们排成一条线，并且依次取 $1\sim n$ 作为编号。

每一张照片可以拍摄到这列奶牛中一个连续的区间中的奶牛。对于每一头奶牛，FJ 都想要让它至少出现在一张照片里。

不幸的是，有 $k$ 对关系不好的奶牛，他们拒绝出现在同一张照片里。已知所有关系不好的奶牛所在的位置，请计算出 FJ 需要的最小需要拍摄的照片数量。

输入格式

第一行：两个整数 $n,k$。

第 $2\sim 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\le 10^9$，$1\le k\le 1000$，$1\le a_i, b_i\le n$。