== include(page="template/taskheader" task_id="turism") ==

Zaharel a devenit primar in orasul sau, iar prima masura pe care o va lua va fi dezvoltarea turismului. In oras exista $N$ obiective turistice legate intre ele prin $M$ strazi cu sens unic. Pentru a atrage cat mai multi turisti in orasul sau trebuie sa existe posibilitatea formarii unui traseu turistic astfel: se pleaca de langa un obiectiv turistic, se parcurge fiecare strada exact o data si se revine in locul din care s-a plecat, trecand prin toate obiectivele turistice cel putin odata. ( Ideal ar fi sa se poata construi un traseu care sa viziteze fiecare obiectiv turistic doar o data, dar aceasta problema este prea grea :) ).

Zaharel a devenit primar in orasul sau, iar prima masura pe care o va lua va fi dezvoltarea turismului. In oras exista $N$ obiective turistice legate intre ele prin $M$ strazi cu sens unic. Pentru a atrage cat mai multi turisti in orasul sau trebuie sa existe posibilitatea formarii unui traseu turistic astfel: se pleaca de langa un obiectiv turistic, se parcurge fiecare strada exact o data si se revine in locul din care s-a plecat, trecand prin toate obiectivele turistice cel putin odata (ideal ar fi sa se poata construi un traseu care sa viziteze fiecare obiectiv turistic doar o data, dar aceasta problema este prea grea {:)}).

h2. Cerinta

* Pentru un test se va acorda $30%$ din punctaj daca se determina corect numarul $K$ de strazi suplimentare, $70%$ din punctaj daca se determina si un set de $K$ strazi care respecta conditiile din enunt, respectiv $100%$ din punctaj daca setul de $K$ muchii este minim din punct de vedere lexicografic.
* Un set de strazi $S1 = (a1,b1)(a2,b2)...(aK,bK)$ este mai mic din punct de vedere lexicografic decat alt set de strazi $S2 = (c1,d1)(c2,d2)...(cK,dK)$ daca exista o pozitie $1 &le; p &le; K$ astfel incat $ap < cp$ sau $ap = cp$ si $bp < dp$, iar $(ai,bi) = (ci,di)$ pentru $1 &le; i < p$.

h2. Exemplu

h2. Exemplu

table(example). |_. turism.in |_. turism.out |
| 6 7

h3. Explicatie

!>problema/turism?figura.jpg! Un traseu turistic valid este:

!problema/turism?turism.jpg!
 
Un traseu turistic valid este:

(1,2)(2,3){*(3,1)*}(1,3)(3,5){*(5,4)*}(4,6)(6,5){*(5,4)*}(4,5){*(5,1)*}
== include(page="template/taskfooter" task_id="turism") ==

1912