ФД хочет сфотографировать все свои N коров (2 <= N <= 1,000,000,000), которые выстроились в линию и последовательно пронумерованы от 1 до N. Каждая фотография может вместить некоторый последовательный диапазон коров, и ФД хочет, чтобы каждая корова была, как минимум, на одной фотографии.
К несчастью, имеется K недружественных пар коров (1 <= K <= 1000), которые отказываются находиться на одной фотографии. Вам даны позиции этих недружественных пар коров, определите минимальное количество фотографий, которые придется сделать ФД.
PROBLEM NAME: photo
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и K.
* Строки 2..K+1: Строка i+1 содержит два целых числа, Ai и Bi, указывающих, что коровы на позициях Ai и Bi недружественные, и поэтому не могут быть на одной и той же фотографии.
Формат выходных данных
* Файл 1: Одно целое число, указывающее минимальное количество фотографий, которые должен сделать ФД
Примечание
ФД должен сделать 3 фотографии: - Одна в диапазоне от 1 до 2. - Одна в диапазоне от 3 до 5. - Одна в диапазоне от 6 до 7.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 3
1 3
2 4
5 6
|
3
|