Uolevi on kuullut Maijalta, että GNU/Linux on parempi käyttöjärjestelmä kuin DOS. Hän ei kuitenkaan halua asentaa valmista Linux-jakelua tai käyttää pakettimanageria, vaan asentaa järjestelmän käsin.

Uolevi yritti ensin vain asentaa kaikki tarvittavat ohjelmat siinä järjestyksessä kun ne tulivat mieleen, mutta sitten hän törmäsi ongelmaan: jotkin ohjelmat tarvitsevat toisia ohjelmia asentuakseen.

Tehtävänäsi on selvittää, missä järjestyksessä Uolevi voi asentaa ohjelmat siten, että jokaisen ohjelman riippuvuudet asennetaan ennen sitä.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluvut n ja m, ohjelmien lukumäärä ja riippuvuuksien lukumäärä. Ohjelmat numeroidaan luvuilla 1\ldots n.

Seuraavat m riviä sisältävät ohjelmien väliset riippuvuudet. Jokaisella rivillä on kaksi lukua a ja b, mikä tarkoittaa että ohjelma b riippuu ohjelmasta a, ts. ohjelma a on asennettava ennen ohjelmaa b.

Tuloste

Mikäli ohjelmat on mahdollista asentaa jossain järjestyksessä, tulosta rivi joka sisältää jonkin mahdollisen järjestyksen.

Muussa tapauksessa tulosta QAQ.

Rajat

• 2\leq n \leq 10^5
• 1\leq m \leq 10^5
• 1\leq a, b \leq n
• a\neq b

Esimerkki

Syöte:

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

Tuloste:

5 2 3 4 6 1

Myös mikä tahansa muu lukujen 1\ldots 6 permutaatio, jossa esiintyy 5 ennen 2, 2 ennen 4, 5 ennen 3, 3 ennen 4, 3 ennen 1, 2 ennen 1, kelpaa vastaukseksi.