On vuosi 2080. Uolevi on jo eläkkeellä, ja hän on kulttuurimatkalla Kaliningradissa, joka ennen tunnettiin nimellä Königsberg. Kaupunki muodostuu monesta saaresta, ja niiden välillä kulkee siltoja.

Uolevi muistaa jo nuorena kuulleensa mielenkiintoisen ongelman Königsbergin silloista. Ongelmassa kysytään, mitä reittiä tulee kulkea, jos haluaa käydä läpi kaikki Königsbergin sillat, käyden jokaisessa tasan kerran, ja päätyä takaisin samalle saarelle kuin mistä aloitti.

1700-luvun Königsbergissä tämänlaista reittiä ei löytynyt, mutta kaupunki on kasvanut niistä ajoista paljon. Uolevi haluaisi käydä sillat läpi tällä tavalla, mikäli se on mahdollista.

Syöte

Syötteenä annetaan luvut n ja m, saarten määrä ja siltojen määrä. Saaret numeroidaan luvuilla 1\ldots n. Seuraavat m riviä sisältävät sillat. Jokaisesta sillasta ilmoitetaan saaret, jotka se yhdistää. Samojen saarten välillä voi kulkea useampi silta. Jokaiselta saarelta pääsee siltoja pitkin jokaiselle toiselle saarelle.

Tuloste

Tulosta QAQ, mikäli reittiä ei löydy. Muussa tapauksessa tulosta siltojen järjestysnumerot, jokainen omalle rivilleen (m lukua väliltä 1\ldots m, jokainen täsmälleen kerran). Reitin tulee alkaa solmusta 1 ja lopuksi palata solmuun 1.

Rajat

• 2\leq n\leq 5\cdot 10^4
• 1\leq m\leq 5\cdot 10^4

Esimerkki

Syöte:

4 5
1 2
1 3
2 3
1 4
1 4

Tuloste:

1
3
2
5
4