johnie

Intr-o tara indepartata traia Johnie Walker, un personaj caruia ii placeau foarte mult plimbarile. In tara lui Johnie Walker exista N orase (numerotate de la 1 la N), iar intre anumite perechi de orase exista poteci. Johnie are dorinta de a umbla pe fiecare poteca din tara sa. Astfel, el s-a hotarat sa faca o mare plimbare, desfasurata in mai multe etape. In fiecare etapa Johnie porneste din orice oras din tara, parcurge un anumit drum si se opreste in ce oras doreste. Un drum este reprezentat de un sir de orase, astfel incat intre oricare 2 orase consecutive din sir exista o poteca. In plimbarea lui, Johnie doreste sa parcurga fiecare poteca o singura data. Lui ii este indiferent daca trece printr-un oras de mai multe ori, chiar in acelasi drum.

Cerinta

Dandu-se numarul de orase din tara si potecile dintre acestea, se cere sa se determine numarul minim de etape in care Johnie poate parcurge toate potecile. De asemenea, se cere si o modalitate de parcurgere a potecilor, pe etape.

Date de intrare

Pe prima linie a fisierului johnie.in sunt scrise doua numere naturale separate prin spatiu N, reprezentand numarul de orase si M, reprezentand numarul de poteci. Pe fiecare dintre urmatoarele M linii sunt scrise cate doua numere naturale distincte i j (cuprinse intre 1 si N) cu semnificatia ca exista o poteca de la orasul i la orasul j.

Date de iesire

Fisierul de iesire johnie.out va contine pe prima linie un numar natural min care reprezinta numarul minim de etape ale plimbarii. Urmatoarele min linii contin drumurile pe care le parcurge Johnie in fiecare etapa, cate un drum pe o linie. Primul numar de pe linia care descrie un drum reprezinta numarul de orase parcurse in drumul respectiv, iar urmatoarele numere reprezinta orasele parcurse, in ordinea parcurgerii. Numerele scrise pe aceeasi linie sunt separate prin cate un spatiu.

Restrictii si precizari

• 1 <= N <= 50000
• 1 <= M <= 100000
•Intre doua orase pot exista mai multe poteci.
•O poteca este bidirectionala.
•Nu exista poteci ce incep si se termina in acelasi oras.

Exemplu

Timp maxim de executie/test: 0.5 secunde

Daniel Pasaila
Universitatea "Al. I Cuza", Iasi - Facultatea de Informatica
danielpasaila@yahoo.com