Мінімізація максимізатора
Компанія ООО Кріс готує до випуску новий апаратний пристрій, який називається Максимізатор. Максимізатор має 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), відокремлених одним пропуском.
Вихідні дані
Для кожного тесту у окремому рядку вивести довжину найкоротшої підпослідовності сортувальників, які видають таку ж відповідь, що й початкова послідовність сортувальників на усіх можливих вхідних даних.