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<=z<=y.

Írjunk programot, amely kiszámítja, hogy legkevesebb hány futó kell ahhoz, hogy a láng eljusson a cél városig.

A bemenet szöveges állomány első sorában két egész szám található: a két város távolsága (10<=K<=1000) és a jelentkezett futók száma (2<=N<=20000). A további N sor mindegyikében két egész szám van I és E (0<=I<E<=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. (Tehát a futókat 1-től számozzuk.) Feltételezhetjük, hogy a láng eljuttatható a cél városig a jelentkezett futókkal.

A kimeneti 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ó.

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

A feladat forrása: NTOITV 2008/2009 III. kategória, 2. forduló

Algoritmusok: mohó algoritmus