Šeštadieninė informatikos olimpiadininkų mokykla

Pavasarį Šeštadieninėje olimpiadininkų mokykloje Linas dėsto apie grafų teorijos algoritmus. Taigi jam dažnai tenka lentoje nubrėžti vienokį ar kitokį grafą. Būdamas šiek tiek tingus (kaip ir visi informatikai), Linas nemėgsta daug mosikuoti rankomis. Todėl brėždamas grafą jis norėtų atlikti kuo mažiau rankos judesių, t.y. brėžti grafą neatitraukdamas rankos nuo lentos, ir nebrėždamas tos pačios briaunos kelis kartus.

Parašykite programą, kuri, perskaičius grafo aprašymą iš failo, nustatytų, ar jį galima nubrėžti minėtuoju būdu, ir išvestų viršūnių numerių seką, kuriuos jungdamas Linas nubrėš visą grafą.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašyti du sveikieji skaičiai N ir M (, ). N yra grafo viršūnių, o M - briaunų skaičius. Grafo viršūnės sunumeruotos nuo 1 iki N. Sekančios M eilučių apibūdina grafo briaunas: kiekvienoje eilutėje įrašyta skaičių pora ai ir bi (), žyminti, jog šias dvi viršūnes grafe jungia briauna.

Rezultatai

Pirmoje rezultatų failo eilutėje turi būti įrašytas žodis TAIP, jei Linas gali nubrėžti šį grafą minėtuoju būdu, ir žodis NE, priešingu atveju. Jei minėtasis būdas nubrėžti grafą egzistuoja, antroje eilutėje turi būti įrašyta (M + 1) skaičių, atskirtų tarpais, seka ck (). Šie skaičiai reiškia, kad paeiliui jungdamas ck -tąją viršūnę su ck+1 -tąja, Linas nubrėš visą grafą (žr. pavyzdį).

Pavyzdžiai

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

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

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

TAIP
1 2 4 5 2 3 4

4 6
1 2
1 3
1 4
2 3
2 4
3 4

NE

5 3
1 2
1 3
4 5

NE