题目描述

FJ 的农场里新进来 \(n\) 头奶牛，FJ 给他们让它们排成一行，奶牛的序号是从 \(1\) 到 \(n\)，接下来需要给他们分配牛舍。要求分配到每个牛舍的所有奶牛的序号必须是连续的。例如 FJ 可以让序号为 \(5/6/7\) 这 \(3\) 头奶牛分配在一个牛舍，但是不能将 \(4\) 和 \(6\) 单独分配在一个牛舍，因为此时它们的序号不是连续的。但是有些奶牛之间有矛盾，这些奶牛是不能放在一个牛舍中的，否则它们之间会打架。现在有 \(k\) 对奶牛是有矛盾的，FJ 希望在满足不出现奶牛打架的前提下提供的牛舍最少。那么最少需要提供多少间牛舍？

格式

输入格式

输入第 \(1\) 行 \(2\) 个整数 \(n\) 和 \(k\)；

接下来输入 \(k\) 行，每行 \(2\) 个整数 \(a_i\) 和 \(b_i\)，表示一对有矛盾的奶牛编号。

输出格式

输出一行一个整数，表示最少情况下需要提供的牛舍间数。

样例1

样例输入1

7 3
1 3
2 4
5 6

样例输出1

3

来源

地址：\(\text{Online~Judge}\)
作者：\(hoogy\)
模拟赛\(T3\)