- Time limit: 3.00 s
- Memory limit: 512 MB
Bittimaan kuningas järjestää juhlat, joihin kutsutaan paljon arvovaltaisia vieraita läheltä ja kaukaa. Etikettisääntöjen takia vieraiden saapumisjärjestyksessä on rajoitteita. Rajoitteet ovat muotoa "vieraan a tulee saapua juhliin ennen vierasta b".
Bittimaan kuninkaan neuvonantajan tehtävänä on päättää missä järjestyksessä vieraat saapuvat juhliin. Jokainen vieras on lahjonut neuvonantajan päästäkseen juhliin mahdollisimman aikaisin. Vieras 1 on maksanut eniten lahjuksia, sitten vieras 2, sitten vieras 3 ja niin edelleen.
Neuvonantaja valitsee järjestyksen jossa vieras 1 pääsee juhliin mahdollisimman aikaisin. Kaikista tällaisista järjestyksistä neuvonantaja valitsee sen jossa vieras 2 pääsee juhliin mahdollisimman aikaisin, tällaisesta sen jossa vieras 3 pääsee juhliin mahdollisimman aikaisin jne. Tehtäväsi on löytää järjestys jonka neuvonantaja valitsi.
Syöte
Syötteen ensimmäisellä rivillä on kaksi lukua, n ja m, vieraiden määrä ja rajoitteiden määrä. Jokaisella seuraavalla m:llä rivillä on kaksi lukua a ja b, jotka tarkoittavat että vieraan a tulee saapua juhliin ennen vierasta b.
Syötteissä on aina olemassa ainakin yksi validi järjestys.
Tuloste
Tulosta n lukua, järjestys jonka neuvonantaja valitsi.
Rajat
- 2 \le n \le 10^5
- 1 \le m \le 2 \cdot 10^5
- 1 \le a, b \le n, a \neq b
Esimerkki
Syöte:
3 1 3 1
Tuloste:
3 1 2
Syöte:
5 6 2 1 5 2 4 1 5 4 3 1 5 3
Tuloste:
5 2 3 4 1
Syöte:
6 6 6 5 6 4 5 2 4 3 3 1 2 1
Tuloste:
6 5 2 4 3 1