Šeštadieninė informatikos olimpiadininkų mokykla

Mechiko miestas įkurtas gražiame slėnyje, kuriame prieš daugelį metų tyvuliavo ežeras. Apie 1300 metus actekų žyniai nusprendė pripilti ežero viduryje žemių ir įkurti imperijos sostinę. Miestas vėliau išsiplėtė ir ežero dabar nebėra.

Iki atsikeliant actekams ežero krantuose buvo įkurta c miestų. Kai kurie šių miestų buvo sudarę prekybos sutartis. Tarp šių miestų valtimis buvo plukdomos prekės. Iš bet kurio miesto buvo galima ežeru nuplaukti į bet kurį kitą miestą plaukiant tuos miestus jungiančia atkarpa.

Galiausiai miestų valdytojai nusprendė pagerinti prekybą. Jie suprojektavo prekybinį maršrutą, kuris sujungė visus aplink ežerą esančius miestus. Maršrutas tenkino tokius reikalavimus:

• Galėjo prasidėti bet kuriame mieste, apėjo visus miestus ir baigėsi bet kuriame kitame (t. y. ne pradiniame) mieste.
• Kiekvienas miestas turėjo būti aplankytas lygiai vieną kartą.
• Kiekviena gretimų maršruto miestų pora buvo pasirašiusi tarpusavio prekybos sutartį.
• Kiekviena gretimų maršruto miestų pora buvo sujungta atkarpa.
• Siekiant išvengti laivų susidūrimų, nei vienoje vietoje maršrutas pats savęs nekirto.

Paveiksle pavaizduotas ežeras ir aplink jį esantys miestai. Linijos (ir plonos, ir storos) vaizduoja miestų tarpusavio prekybos susitarimus. Storos linijos vaizduoja prekybinį maršrutą, prasidedantį 2 mieste ir pasibaigiantį 5-ame mieste.

Šis maršrutas nekerta pats savęs. Jei, pavyzdžiui, maršrute būtų miestų grandinė , tai toks maršrutas būtų nekorektiškas, nes jis kirstų pats save.

Miestai aplink ežerą sunumeruoti nuo 1 iki c laikrodžio rodyklės kryptimi.

Duotas miestų skaičius c ir sąrašas miestų, sudariusių tarpusavio prekybos sutartis. Parašykite programą, kuri sudarytų prekybinį maršrutą, tenkinantį aukščiau išvardintus reikalavimus.

Pradiniai duomenys

Pirmoje eilutėje įrašytas sveikasis skaičius c (). Antroje eilutėje įrašytas sveikasis skaičius n – prekybos sutarčių skaičius. Kiekviena iš tolesnių n eilučių nusako vieną prekybinį susitarimą tarp dviejų miestų. Joje yra du tarpu atskirti sveikieji skaičiai – sutartį sudariusių miestų numeriai.

Rezultatai

Jei prekybinį maršrutą sukonstruoti įmanoma, tai išveskite c eilučių, kiekvienoje jų po vieną sveikąjį skaičių – miesto numerį. Miestai turi būti išvardinti tokia tvarka, kokia juos numatoma apeiti sukonstruotame maršrute.

Jei reikalavimus atitinkančio prekybinio maršruto sukonstruoti neįmanoma, tuomet išveskite vieną eilutę, kurioje įrašytas skaičius -1.

Pavyzdys

7
9
1 4
5 1
1 7
5 6
2 3
3 4
2 6
4 6
6 7

2
3
4
1
7
6
5