Î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
police.in
police.out
7 9
1 2
1 3
1 4
2 3
2 4
3 4
5 6
6 7
5 7
4
1
2 3 1
1 2 3 4 1
2 3 4 2
5 6 7 5
prof. Dana Lica
Colegiul National “Ion.Luca Caragiale” Ploiesti
Contact: danal182001@yahoo.com