Lino uždavinys

Pradinių duomenų failas:

lin.in  

Rezultatų failas:

lin.out  

Laiko apribojimas:

5 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

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 (1 <= N <= 100, 0 <= M <= N(N-1) / 2). 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 \(a_{i}\) ir \(b_{i}\) (1 <= \(a_{i}\) < \(b_{i}\) <= N), ž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 \(c_{k}\) (1 <= \(c_{k}\) <= N). Šie skaičiai reiškia, kad paeiliui jungdamas \(c_{k}\) -tąją viršūnę su \(c_{k+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