Maksimizatorun minimallaşdırılması
Şirkət MMC Kris yeni bir cihaz, Maksimizator adlı, təqdim etməyə hazırlaşır. Maksimizatorun n girişi var və bunlar 1-dən n-ə qədər nömrələnib. Hər girişə bir tam ədəd təyin edilir. Maksimizatorun bir çıxışı var və bu çıxış, girişlərdən ən böyük dəyəri göstərir.
Maksimizator, Sorter(i[1], j[1]), ..., Sorter(i[k], j[k]) ardıcıllığı ilə işləyir. Hər sorterləyici n giriş və n çıxışa malikdir. Sorter(i, j) funksiyası, i, i + 1, ..., j aralığındakı girişləri artan qaydada sıralayır, digər girişlər isə dəyişməz olaraq çıxışa ötürülür. Maksimizatorun çıxışı, onun son sorterləyicisinin n-ci çıxışıdır.
Bir intern (keçmiş ACM iştirakçısı) müşahidə etdi ki, bəzi sorterləyiciləri ardıcıllıqdan çıxarmaqla da maksimizator düzgün nəticə verə bilər. Maksimizatorun bütün mümkün giriş məlumatları üçün düzgün cavab verən sorterləyicilərin ən qısa alt ardıcıllığının uzunluğunu tapın.
Giriş Məlumatları
Giriş bir neçə testdən ibarətdir. Hər testin ilk sətiri iki tam ədəd n və m (2 ≤ n ≤ 50000, 1 ≤ m ≤ 500000) ehtiva edir. Burada n girişlərin sayını, m isə ardıcıllıqda olan sorterləyicilərin sayını göstərir. Sorterləyicilərin ilkin vəziyyəti növbəti m sətirdə verilir. k-cı sətir k-cı sorterləyicinin parametrlərini ehtiva edir: bir boşluqla ayrılmış iki tam ədəd i[k] və j[k] (1 ≤ i[k] < j[k] ≤ n).
Çıxış Məlumatları
Hər test üçün ayrıca sətirdə, ilkin sorterləyicilər ardıcıllığı ilə eyni nəticəni verən sorterləyicilərin ən qısa alt ardıcıllığının uzunluğunu çıxarın.