Фермер Джон решил собрать панорамное фото ряда из своих N (1 <= N <= 200,000) коров, пронумерованных от 1 до N. Он сделал M M (1 <= M <= 100,000) снимков, каждый из которых покрывает непрерывный диапазон коров. Снимок i содержит коров с номерами от ai до bi включительно. Коллективное фото может и не покрывать каждую отдельную корову.
ФД заметил интересный феномен: каждый снимок содержит ровно одну корову с пятном. Основываясь на данных снимков, определите максимально возможное количество коров с пятнами. Выведите -1, если невозможно назначить пятна коровам так, чтобы соответствовать данным о снимках.
PROBLEM NAME: photo
Формат входных данных
* Строка 1: Два целых числа N и M.
* Строки 2..M+1: Строка i+1 содержит ai и bi.
Формат выходных данных
* строка 1: Максимально возможное количество коров с пятнами у ФД, или -1, если решения нет.
Примечание
Из последней фотографии мы получаем, что корова 3 или корова 4 обязательно должны быть с пятном. При любом выборе будет выполнено свойство и для первых двух снимков.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
1 4
2 5
3 4
|
1
|