nessie

Aţi auzit despre Nessie? Este un pleziozaur misterios care trăieşte în adâncurile lacului Loch Ness din munţii Scoţiei. Cu mulţi ani în urmă el a fost zărit pentru prima oară la suprafaţa lacului, iar de atunci, spre desfătarea turiştilor, el îşi face apariţia în mod periodic.
Nessie ştie de la managerii Loch Ness care este programul de vizitare a lacului pentru un interval de $N$ zile. Mai exact, el cunoaşte datele primei și ultimei zile de şedere în preajma lacului pentru fiecare turist.
Contractul pe care Nessie l-a semnat cu managerii prevede faptul că fiecare dintre turişti trebuie să aibă posibilitatea să-l zărească, însă doar de departe şi doar o singură dată, deoarece Nessie intenţionează să rămână în continuare misterios. Pot exista zile fără turişti şi în aceste zile Nessie profită de fiecare dată ca să iasă la suprafaţa lacului.

Cerinţă

Cunoscând prima şi ultima zi de şedere pentru fiecare turist, şi numărul total de zile prevăzute în contract, determinaţi numărul maxim de ieşiri la suprafaţa lacului, pe care Nessie le poate face, astfel încât fiecare turist să-l zărească o singură dată.

Date de intrare

Fişierul de intrare nessie.in conține pe prima linie numerele naturale $N$ și $T$, separate printr-un spațiu, unde $N$ este numărul de zile prevăzute în contract iar $T$ este numărul de turişti. Pe următoarele $T$ linii se află câte două valori naturale separate prin câte un spațiu. Numerele $a_i$ şi $b_i$ de pe linia $i + 1$ reprezintă prima, respectiv ultima zi de şedere în preajma lacului Loch Ness pentru turistul $i$.

Date de ieșire

Fişierul de ieșire nessie.out conţine pe prima linie un număr natural care reprezintă numărul maxim de apariţii ale lui Nessie pe suprafaţa lacului, astfel încât fiecare turist să-l zărească o singură dată.

Restricţii şi precizări

• $2 \leq N, T \leq 250 \ 000$
• $1 \leq a_i \leq b_i \leq N$
• Pot exista mai mulți turiști care vizitează lacul în aceeași perioadă
• În cazul în care nu există soluţie se va afişa IMPOSIBIL
• Nessie iese la suprafaţa lacului cel mult odată pe zi

Exemplul 1

nessie.in

5 2
1 3
4 5

nessie.out

2

Explicaţie

Nessie poate ieşi la suprafaţă o dată în una din zilele $1$, $2$ sau $3$ pentru primul turist şi încă odată în ziua $4$ sau în ziua $5$ pentru al doilea turist.

Exemplul 2

nessie.in

7 3
2 5
3 4
6 7

nessie.out

3

Explicaţie

Nessie poate ieşi în ziua $1$, când nu sunt turişti, mai poate ieşi odată în ziua $3$ sau ziua $4$ pentru primul şi al doilea turist şi a treia oară în ziua $6$ sau ziua $7$ pentru al treilea turist.

Exemplul 3

nessie.in

7 3
3 5
1 4
6 7

nessie.out

3

Explicaţie

Nessie poate ieşi în ziua $1$ pentru al doilea turist, în ziua $5$ pentru primul turist și în ziua $6$ sau $7$ pentru al treilea turist.

Exemplul 4

nessie.in

6 3
1 6
2 3
4 5

nessie.out

IMPOSIBIL

Explicaţie

Nessie nu poate ieși la suprafață atât pentru turistul $2$ cât și pentru turistul $3$ fără să fie zărit de două ori de către primul turist.