Staféta
Az olimpiai lángot egy kiindulási városból a cél városba kell eljuttatni. A két város távolsága $K$ kilométer. Sok futó jelentkezett, mindegyikről tudjuk, hogy hányadik kilométertől hányadik kilométerig vállalja a futást. Ha egy futó az $x$ kilométertől az $y$ kilométerig vállalja a futást, akkor minden olyan futó át tudja venni tőle a lángot, aki olyan $z$ kilométertől vállalja a
futást, hogy $x\leq z\leq y$.
Feladat
Írj programot (STAFETA.PAS, ...), amely kiszámítja, hogy legkevesebb hány futó kell
ahhoz, hogy a láng eljusson a cél városig.
Bemenet
A STAFETA.BE szöveges állomány első sorában két egész szám található: a két város távolsága $(10\leq K\leq 1000)$ és a jelentkezett futók száma $(2\leq N\leq 20000)$. A további $N$ sor mindegyikében két egész szám van $I$ és $E$ ($0\leq I < E \leq K$) ami azt jelenti, hogy egy futó az $I$-edik kilométertől az $E$-edik kilométerig vállalja a láng továbbítását. A futókat a sorszámukkal azonosítjuk, a bemenet $j+1$-edik sorában a $j$-edik futó adata van. Feltételezhetjük, hogy a láng eljuttatható a cél városig a jelentkezett futókkal.
Kimenet
A STAFETA.KI szöveges állomány első sorába a láng célba juttatásához minimálisan
szükséges futók $M$ számát kell írni. A második sor pontosan $M$ számot tartalmazzon (egy-egy szóközzel elválasztva), azon futók sorszámait, akik teljesítik a feladatot. Tehét a felsorolásban a $j$-edik futó a $j+1$-edik futónak adja át a lángot. Több megoldás esetén bármelyik megadható.
Példa
| STAFETA.BE | STAFETA.KI |
40 7
2 21
25 35
20 34
0 10
5 18
3 7
34 40
|
4
4 1 3 7
|
Tesztadatok
