Задача: Photo

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

Ваш ответ: