obilazak

Maja i Jaca u pauzama citanja casopisa "Cosmopolitan", "Vogue", "Joy", "Viva", "Bravo" i "Lepota i zdravlje" igraju veoma zanimljivu igru. Jaca na listu papira, tako da Maja ne vidi, nacrta konveksan mnogougao sa n strana i obeleži temena brojevima 1, 2, ..., n na proizvoljan nacin, a zatim docrta i m dijagonala, ali tako da se one ne seku (sem možda u temenima). Posle toga Jaca kaže Maji sve parove temena koja su krajnja temena bilo stranice ili dijagonale, ali joj ne kaže koji parovi temena su krajevi stranice, a koja su krajevi dijagonale. Maja treba da pogodi redosled temena obilazeci redom stranice mnogougla. Pomozite ljupkoj plavookoj i plavokosoj Maji da pobedi. <br><br>

Ulaz: U prvom redu ulaza se nalaze brojevi n i m (3 <= n <= 10000, 0 <= m <= n–3). U sledecih n + m redova nalaze se po dva broja, koji oznacavaju par temena koja su spojena stranicom ili dijagonalom. Zadati redosled stranica i dijagonala je proizvoljan. <br><br>
Izlaz: Izlaz treba da se sastoji od n redova od kojih svaki sadrži tacno jedan broj. Ovi brojevi treba da predstavljaju redosled obilaska temena iduci po stranicama mnogougla. Rešenje nije jedinstveno – uvek postoji 2n ravnopravnih rešenja u zavisnosti od izabranog pocetnog temena i smera obilaska. <br><br>
Primer: <br><br>
ulaz<br>
5 2<br>
2 4<br>
5 1<br>
1 2<br>
3 5<br>
1 3<br>
2 3<br>
4 1<br><br>

Izlaz<br>2<br>3<br>5<br>1<br>4<br><br><img src="./tasks/obilazak/obilazak.gif">