police      

Într-un municipiu, noul sef al Politiei Circulatie încearca sa micsoreze numarul de subalterni care stau fara sarcini concrete în birouri. În acest scop doreste sa trimita pe teren cât mai multi politisti, pentru a supraveghea strazile orasului. In oras exista m strazi si n intersectii. Intersectiile sunt numerotate de la 1 la n. O strada uneste doua intersectii si este identificata prin cele doua intersectii care o delimiteaza.
Seful considera ca va controla mai usor politistii daca va repartiza fiecaruia acelasi tip de traseu. Prin traseu el întelege o succesiune de intersectii care respecta urmatoarele conditii:
- intre oricare doua intersectii consecutive pe traseu exista o strada de legatura;
- din orice interesctie a traseului s-ar afla, politistul poate sa strabata toate strazile acestuia, trecand pe fiecare strada o singura data si revenind în intersectia de plecare;
- traseu repartizat oricarui politist trebuie sa contina cel putin o strada nesupravegheata de restul politistilor aflati în patrulare.
Un politist va parcurge numai strazile de pe traseul lui.

Cerinta
Scrieti un program care sa determine numarul maxim de politisti care pot fi trimisi pe teren si traseele repartizate fiecaruia.

Date de intrare
Fisierul de intrare police.in are urmatoarea structura:   
- pe prima linie sunt scrise doua numere naturale separate prin spatiu n m, reprezentând numarul de intersectii din oras si respectiv numarul strazilor;
- urmatoarele m linii contin informatii despre cele m strazi, cate o strada pe o linie; pentru fiecare strada sunt scrise doua numere naturale cuprinse intre 1 si n separate printr-un spatiu, reprezentând cele doua intersectii care delimiteaza strada respectiva.

Date de iesire
Fisierul de iesire police.out va avea urmatoarea structura:   
- pe prima linie se scrie numarul p care reprezinta numarul maxim de politisti care pot fi trimisi pe teren;
- pe urmatoarele p linii se vor scrie traseele repartizate politistilor, cate un traseu pe o linie; pentru fiecare traseu se vor preciza intersectiile aflate pe acesta, oricare doua intersectii consecutive fiind separate prin cate un spatiu.

Restrictii
1 < n <= 1500
0 < m <= 4000
În cazul în care exista mai multe solutii, se va furniza una singura.
Între oricare doua intersectii poate exista cel mult o strada.

Exemplu

Timp maxim de executie/test : 0.3 secunde

prof. Dana Lica
Colegiul National “Ion.Luca Caragiale” Ploiesti
Contact: danal182001@yahoo.com