Intervallar#2945
Əsl ox üzərində hər birinin ucları tam ədədlərə düşən interval verilmişdir. Bu uclar intervala daxil deyil. Sizə hansı intervalların kəsişdiyi, hansının isə kəsişmədiyi barədə informasiya verilir. Bu məlumata əsaslanaraq bütün intervaların mümkün olan ən kiçik cəmi uzunluğunu tapın. Qeyd: hər intervalın uzunluğu ən azı olmalıdır.
Birinci sətirdə iki tam ədəd verilir: (1 \leq n \leq 1234) — intervaların sayı və (0 \leq m \leq n(n-1)/2) — kəsişən interval cütlərinin sayı. Növbəti sətirdə kəsişən cütlərin indeksləri verilir. Intervalar -dan n-1-ə kimi nömrələnir. Siyahıda olmayan cütlər kəsişmir. Zəmanət verilir ki, verilmiş informasiyaya uyğun interval sistemi qurmaq mümkündür.
Bütün intervaların mümkün olan ən kiçik cəmi uzunluğunu çap edin. Heç bir interval sıfır uzunluqlu ola bilməz.
Nümunə 1