Минимизация максимизатора
Компания ООО Крис готовит к выпуску новое аппаратное устройство, которое называется Максимизатор. Максимизатор имеет n входов, пронумерованных от 1 до n. На каждый вход подается одно целое число. Максимизатор имеет один выход, представляющий собой наибольшее значение среди входов максимизатора.
Максимизатор реализован как последовательность сортировщиков Sorter(i[1], j[1]), ..., Sorter(i[k], j[k]). Каждый сортировщик имеет n входов и n выходов. Sorter(i, j) сортирует данные на входах i, i + 1, ..., j в неубывающем порядке, а данные с остальных входов проходят на выход неизмененными. Выходом максимизатора является n-ый выход его последнего сортировщика.
Интерн (бывший участник ACM) заметил, что из последовательности можно исключить некоторые сортировщики так, чтобы максимизатор выдавал правильный результат. Найти длину кратчайшей подпоследовательности сортировщиков, которые все еще выдают правильные ответы для всех возможных комбинаций входных данных.
Входные данные
Состоит из нескольких тестов. Первая строка каждого теста содержит два целых числа n и m (2 ≤ n ≤ 50000, 1 ≤ m ≤ 500000). Число n задает количество входов, а m - количество сортировщиков в последовательности. Начальное состояние сортировщиков описывается следующими m строками. k-ая строка содержит параметры k-го сортировщика: два целых числа i[k] и j[k] (1 ≤ i[k] < j[k] ≤ n).
Выходные данные
Для каждого теста в отдельной строке вывести длину кратчайшей подпоследовательности сортировщиков, выдающих тот же ответ, что и исходная последовательность сортировщиков на всех возможных входных данных.