VU algoritmavimo seminaras (iki 2005)

Butus remontuojantis meistras kitam mėnesiui gavo didelį užsakymą ir viską suskirstė į N atskirų darbų. Tačiau kai kurie darbai tarpusavyje priklausomi. T.y. konkretų darbą galima vykdyti tik tada, kai atlikti vienas ar keli kiti darbai. Pavyzdžiui, sienas dažyti galima tik tada, kai jos nuglaistytos ir nugruntuotos.

Jei darbą a būtina atlikti prieš pradedant vykdyti darbą b, tai sakysime, kad darbai a ir b sudaro priklausomą porą.

Darbų rinkinys yra korektiškas, t.y. jame nėra tokios priklausomų darbų porų grandinės, kuri sudarytų ciklą.

Užduotis. Žinomas darbų skaičius ir priklausomų darbų poros. Parašykite programą, kuri nustatytų, kokia tvarka reikia atlikti tuos darbus. Darbų eiliškumas turi būti toks, kad darbas a būtinai būtų atliktas prieš darbą b, jei tik a ir b sudaro priklausomą porą.

Jei galimi keli sprendiniai, reikia pateikti bet kurį.

Pradiniai duomenys pateikiami byloje darbai.in. Pirmoje eilutėje įrašyti du sveikieji skaičiai N ir P. Čia N – darbų skaičius (1 ≤ N ≤ 250), P – priklausomų porų kiekis. Laikoma, kad darbai sunumeruoti nuo 1 iki N.

Likusiose P eilučių įrašyta po du sveikuosius skaičius a ir b (1 ≤ a, b ≤ N). Šie skaičiai reiškia, kad darbai a ir b sudaro priklausomą porą, t.y. kad darbą b galima pradėti tik tada, kai darbas a jau yra atliktas. Ta pati pora pradiniuose duomenyse sutinkama tik vieną kartą.

Rezultatai – N sveikųjų skaičių (darbų numeriai išdėstyti ta tvarka, kuria juos reikėtų atlikti) įrašomi į bylą darbai.out po vieną skaičių į eilutę.

Pavyzdys

4 4
4 2
3 1
4 3
4 1

4
3
2
1