Državno natjecanje iz informatike Srednja škola / Druga podskupina (3. i 4. razred) / Drugi dan natjecanja - 2. zadatak

Prvi dan natjecanja prošao je očekivano, uz sitno kašnjenjenje objave rezultata jer organizatori nisu mogli pronaći selotejp kojim bi se papiri s rezultatima zalijepili na pano ispred dvorane.

Glavni krivac u ovoj priči bio je Joško koji se u jednom kutu dvorane igrao selotejpom lijepeći komadiće na stol.

Preciznije, Joško je nalijepio ukupno N komadića selotejpa po dužini stola, lijepeći ih jedan po jedan i to tako da je prvi selotejp zalijepio preko cijele dužine stola, a za svaki sljedeći poznate su koordinate Li i Ri koje predstavljaju udaljenost lijevog i desnog kraja selotejpa od početnog ruba stola.

Kad je Boško, usred pritiska od strane nestrpljivih mentora, saznao za Joškovu razbibrigu, ljutito mu je uzeo selotejp iz ruku i naredio da što prije počisti nered koji je napravio.

Joško u svakom koraku može odabrati komadić selotejpa koji se vidi na površini stola (koji nije u potpunosti prekriven komadićima koji su zalijepljeni preko njega) i odlijepiti ga, čime će se odlijepiti i svi komadići selotejpa koji su izravno ili neizravno bili zalijepljeni na njega.

U koliko najmanje koraka Joško može odlijepiti sve komadiće selotejpa sa stola?

ULAZNI PODACI

U prvom su retku prirodni brojevi N (1 ≤ N ≤ 100 000), broj komada selotejpa, i D (1 ≤ D ≤ 1 000 000 000), duljina stola.

Slijedi N redaka koji opisuju selotejpe redom kojim su zalijepljeni.

U svakom su retku dva prirodna broja Li i Ri (0 ≤ Li < Ri ≤ D), udaljenosti lijevog i desnog kraja selotejpa od početka stola.

Za prvi selotejp vrijedit će L1 = 0 i R1 = D.

IZLAZNI PODACI

U jedini redak ispišite traženi minimalan broj koraka.

PRIMJERI TEST PODATAKA

Ulaz

4 3
0 3
0 1
2 3
0 3

Izlaz

2

Objašnjenje

Pojašnjenje prvog primjera: Najprije odljepljujemo 4. selotejp (između točaka 0 i 3), nakon čega 1. selotejp postaje vidljiv i njegovim odljepljivanjem skidamo i preostala dva selotejpa.

Ulaz

9 8
0 8
0 5
4 8
0 1
3 4
0 1
4 8
1 4
3 8

Izlaz

3

Objašnjenje

Pojašnjenje drugog primjera: Najprije odljepljujemo 8. selotejp (između točaka 1 i 4) koji sa sobom povlači i 9. selotejp, nakon čega 2. selotejp (između točaka 0 i 5) postaje vidljiv i njegovim odljepljivanjem skidamo sve selotejpe osim prvog koji na kraju (u trećem koraku) odljepljujemo sa

stola.