Usled prevelikog zagađenja vazduha, ljudi su morali da napuste
Zemlju i sada žive u svemirskim stanicama. Navedene civilne
stanice su numerisane brojevima 1, 2, ..., m. Radi odbrane od
vanzemaljaca napravljeno je još
n vojnih stanica. Između svake
vojne i svake civilne stanice moguće je teleportovanje u
tačno jednom smeru (ako je moguće teleportovanje iz stanice
A u stanicu
B nije moguće iz stanice
B u
A). Iz vojne
stanice ili nije moguće teleportovanje ni u jednu civilnu
stanicu ili je moguće teleportovanje u niz uzastopnih civilnih
stanica (npr. iz vojne stanice moguće je teleportovanje u
civilne stanice
k, k + 1, ..., p gde je 1 ≤
k ≤ p ≤
m). Ne može se teleportovati od jedne civilne stanice do druge
civilne, kao i od jedne vojne do druge vojne.
Međutim, vanzemaljci su rešili da osvoje planetu Zemlju. General
Đurić je otkrio da vanzemaljci planiraju da napadnu neku
stanicu X, ali ne zna tačno koju. On je procenio da ako vojsci
treba više od 3 teleportovanja do napadnute stanice X ona
će sigurno pasti u ruke vanzemaljaca. Zato je rešio da nađe
sve vojne stanice sa kojih može da stigne da odbrani sve ostale
stanice i tamo rasporedi vojsku. Kako je ostalo malo vremena -
zamolio je vas mlade programere da mu pomognete.
Ulaz:
(Ulazni podaci se nalaze u datoteci teleport.in) U prvoj liniji ulazne datoteke se nalaze dva
broja n i m (1 ≤ n, m ≤ 5x105) koji redom
predstavljaju broj vojnih i broj civilnih stanica. Zatim sledi n
linija koje opisuju veze između stanica: u i-toj (i = 1, 3,
...,n) liniji se nalaze dva cela broja a[i] i b[i] (0 ≤
a[i] ≤ b[i] ≤ m) koji predstavljaju krajnje civilne stanice
u koje se može teleportovati iz i-te vojne stanice (iz vojne
stanice moguće je teleportovanje u civilne stanice a[i], a[i]
+ 1, ..., b[i]). Ukoliko je je a[i] = b[i] = 0 tada se iz date
vojne stanice direktno ne može stići ni u jednu civilnu
Izlaz:
(Izlazne podatke upisati u datoteku teleport.out) U prvom redu izlazne datoteke se nalazi broj
vojnih stanica koje traži general Đurić, a u drugom lista
tih vojnih stanica razdvojenih jednim razmakom.
Primer 1:
teleport.in
|
|
teleport.out
|
3 4
1 3
2 3
4 4
|
|
2
1 3
|
Objašnjenje.
Vojna stanica 2 ne zadovoljava Đurićevu procenu, jer
najkraći putevi do civilne stanice 1 i vojne stanice 1
zahtevaju više od 3 teleportovanja.
Primer 2:
teleport.in
|
|
teleport.out
|
4 4
1 4
1 3
0 0
2 4
|
|
1 1
|