Fişierul intrare/ieşire:johnie.in, johnie.outSursă.campion 2007
AutorDaniel PasailaAdăugată dedanielpDaniel Pasaila danielp
Timp execuţie pe test0.2 secLimită de memorie20096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Johnie

Intr-o tara indepartata traia Johnie Walker, un personaj caruia ii placeau foarte mult plimbarile. Tara lui era organizata in N orase, iar intre anumite perechi de orase existau poteci. Johnie are dorinta de a umbla pe fiecare poteca din tara sa. Astfel, el s-a hotarat sa faca o mare plimbare intr-un numar de 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, a.i 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.
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 este scris numarul N, reprezentand numarul de orase si M, reprezentand numarul de poteci. Pe urmatoarele M linii sunt scrise perechile (i, j) ce marcheaza existenta unei poteci de la orasul i la orasul j.

Date de iesire

Prima linie a fisierului johnie.out trebuie sa contina numarul minim de etape. Urmatoarele linii contin, cate unul pe linie, drumurile pe care le parcurge Johnie in fiecare etapa. Primul numar dintr-o anumita linie reprezinta numarul de orase parcurse in drumul respectiv, iar urmatoarele numere reprezinta orasele parcurse, in ordine.

Restrictii

  • 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

johnie.injohnie.out
7 7
1 2
1 3
1 4
2 3
3 5
4 5
6 7
2
7 1 4 5 3 2 1 3
2 6 7
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content