Rezolvare PBinfo #2309

La o competiție au participat N concurenți. Fiecare dintre ei a primit un număr de concurs astfel încât să nu existe concurenți cu același număr. Numerele de concurs aparțin mulțimii {1,2,...,N}. Din păcate, clasamentul final a fost pierdut, iar comisia își poate aduce aminte doar câteva relații între unii participanți (de genul “participantul cu numărul 3 a ieșit înaintea celui cu numărul 5”).

Cerința

Șeful comisiei are nevoie de un clasament final și vă cere să-l ajutați determinând primul clasament în ordine lexicografică ce respectă relațiile pe care și le amintește comisia.

Date de intrare

Fișierul de intrare competitie.in conține pe prima linie doua numere naturale nenule N și M, reprezentând numărul concurenților, respectiv numărul relațiilor pe care și le amintește comisia. Pe fiecare din următoarele M linii se află câte două numere naturale nenule i și j, având semnificația: concurentul cu numărul de concurs i a fost în clasament înaintea concurentului cu numărul de concurs j.

Date de ieșire

Fișierul de ieșire competitie.out va conține pe prima linie clasamentul sub forma unui sir de numere naturale nenule nr1, nr2, …, nrN, separate prin câte un spațiu, reprezentând numerele de concurs ale concurenților, în ordine de la primul clasat la ultimul.

Restricții și precizări

• 1 ≤ N, M ≤ 1000
• Se garantează corectitudinea datelor de intrare și faptul ca există totdeauna o soluție.

Exemplul 1:

competitie.in

3 1
1 2

competitie.out

1 2 3

Exemplul 2:

competitie.in

4 2
2 1
3 4

competitie.out

2 1 3 4