Gigel adora jocurile pe calculator. Recent a primit un joc denumit Fighters. In joc apar N personaje (luptatorii), pe care el le-a numerotat de la 1 la N. Jocul i s-a parut dificil si pana acum, oricat a incercat, Gigel nu a reusit sa treaca de primul nivel.
La inceputul jocului Gigel se poate identifica cu oricare dintre luptatori si primeste o piatra fermecata. Pentru a trece la nivelul urmator piatra fermecata trebuie sa ajunga succesiv in posesia fiecarui luptator. Luptatorul care a ramas la sfarsit in posesia pietrei trece la nivelul urmator, iar Gigel se va identifica in continuare cu acesta.
Tot jucand, Gigel a observat ca orice luptator se poate intalni cu orice alt luptator si la o astfel de intalnire se poate isca o lupta. Castigatorul luptei intra in posesia pietrei fermecate, iar cel invins moare. De asemenea Gigel a observat ca de fiecare data cand doi jucatori lupta, rezultatul luptei este predefinit si dupa numeroase incercari, Gigel stie pentru orice pereche de luptatori cine invinge pe cine.

Cerinta

Scrieti un program care determina o modalitate prin care Gigel poate trece la urmatorul nivel al jocului. Programul va decide care este personajul cu care trebuie sa se identifice initial Gigel si succesiunea luptelor care trebuie desfasurate pentru a trece la nivelul urmator.

Date de intrare

Fisierul de intrare joc10.in contine pe prima linie N (numarul de luptatori), iar pe fiecare dintre urmatoarele N*(N-1)/2 linii o pereche de numere naturale x y cu semnificatia "la un conflict luptatorul x este invins de luptatorul y".

Date de iesire

Fisierul de iesire joc10.out contine pe o singura linie ordinea in care luptatorii primesc piatra fermecata. z1 z2 ... zN. Luptatorul z1 este cel care cu care se identifica initial Gigel si care are piatra fermecata.

Restrictii

• 2 <= N <= 1000
• Valorile scrise pe aceeasi linie in fisierele de intrare si iesire sunt separate prin spatii.
• Daca exista mai multe solutii, se va determina una singura.

Exemple

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi