6. O sústredkových pozvánkach

Jarné sústredenie KSP¹ sa pomaly blíži a vedúci začali s prípravami. Prvou, vcelku dôležitou úlohou je pozvať účastníkov. Zobrali sa preto výsledkové listiny oboch kategorií a spojili sa do jednej, čím vznikol dlhý zoznam, podľa ktorého sa bude pozývať na sústredenie. Postupne sa budú oslovovať účastníci od prvého miesta po posledné, až kým prvých 32 účastníkov nepovie, že ide na sústredenie. Je preto jasné, že čím skôr je niekto v tomto zozname, tým má väčšiu šancu, že sa na sústredenie dostane.

To všetko by bolo pekné, vedúci však začali vyjadrovať svoje súkromné preferencie. Napríklad Mišo povedal, že Paulínka musí byť pozvaná skôr ako prvý človek v zozname, aby sa určite dostala na sústredenie. Žaba tiež vyjadril názor, že dievčatá by sa mali uprednostňovať a pozývať protekčne skorej. A Hopko nástojil², aby bol jeho brat Slavo pozvaný na sústredenie skôr ako Andrej.

Aby v tom mala Baška prehľad, spísala si \(m\) požiadaviek vedúcich. Môže sa stať, že sa jedna požiadavka niekoľkokrát opakuje. Každá požiadavka je tvaru "x y" a vyjadruje, že človek, ktorý je v zozname na \(x\)-tej pozícii má byť na sústredenie pozvaný skôr ako človek na \(y\)-tej pozícii. Baška sa teraz zamýšľa, v akom poradí má vlastne pozývať účastníkov z pôvodného zoznamu. Určite chce splniť všetky požiadavky, ktoré majú vedúci. Zároveň ale chce pozvať účastníka, ktorý je na prvom mieste čo najskôr. Z možných poradí, ktoré spĺňajú túto podmienku, chce potom vybrať také, kde pozve účastníka na druhom mieste čo najskôr atď…

Úloha

Máme \(n\) účastníkov očíslovaných \(1\) až \(n\) v poradí, v akom by sa mali pozývať na sústredenie. Ďalej máme \(m\) požiadaviek – dvojíc \(x_i\) a \(y_i\). Nájdite takú permutáciu čísel \(1\) až \(n\), že pre všetky \(i\) je číslo \(x_i\) pred číslom \(y_i\). Spomedzi takýchto permutácií vyberte tú, v ktorej je číslo \(1\) najskôr ako sa (za splnenia všetkých požiadaviek) dá, číslo \(2\) je najskôr ako sa (za splnenia všetkých predošlých podmienok) dá, a tak ďalej až po \(n\).

Formát vstupu

Na prvom riadku sa nachádzajú dve čísla \(n\) a \(m\) (\(1 \leq n \leq 200\,000\), \(1 \leq m \leq 400\,000\)) – počet účastníkov a počet požiadaviek. Nasleduje \(m\) riadkov, každý obsahuje dvojicu čísel \(x_i\) a \(y_i\) (\(1 \leq x_i, y_i \leq n\)).

Vstupné súbory sú pomerne veľké. Odporúčame preto používať C++ (keďže Python nemusí stíhať ani pri optimálnej časovej zložitosti) a na načítavanie odporúčame použiť knižnicu cstdio.

Formát výstupu

Na jeden riadok vypíšte \(n\) medzerami oddelených čísel – permutáciu spĺňajúcu podmienky zo zadania. Je zaručené, že aspoň jedna takáto permutácia existuje.

Príklad

Input:

4 1
3 1

Output:

3 1 2 4

Účastníka 1 nevieme pozvať ako prvého, ale ak najskôr pozveme účastníka 3, tak ho môžeme pozvať už ako druhého. Následne chceme najskôr pozvať účastníka 2 a až potom 4.

Input:

5 6
3 1
5 1
5 2
1 4
5 4
3 1

Output:

3 5 1 2 4