CSES - Asennus
  • Time limit: 4.00 s
  • Memory limit: 128 MB
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.