turism

Turism

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

Poveste si cerinta...

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
 
Scrieti un program pentru Zaharel care sa determine numarul minim de strazi suplimentare care trebuie construite in oras astfel incat sa existe posibilitatea formarii unui traseu turistic.

h2. Date de intrare

...

Fisierul de intrare $turism.in$ contine pe prima linie numerele naturale $N$ si $M$. Urmatoarele $M$ linii contin perechi de numere intregi $a b$ separate prin spatii cu semnificatia ca exista un o strada cu sens unic de la obiectivul turistic $a$ la obiectivul turistic $b$.

h2. Date de iesire

...

Fisierul de iesire $turism.out$ va contine pe prima linie un singur numar intreg $K$ reprezentand numarul minim de strazi suplimentare care trebuie construite in oras astfel incat sa existe posibilitatea formarii unui traseu turistic. Urmatoarele $K$ linii contin perechi de numere intregi $a b$ separate prin spatii cu semnificatia ca se va construi o strada cu sens unic de la obiectivul turistic $a$ la obiectivul turistic $b$.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 30 000$
* $0 ≤ M ≤ 100 000$
* Obiectivele turistice sunt numerotate cu numere intregi de la $1$ la $N$
* Pot exista mai multe strazi cu sens unic intre doua obiective.
* 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 |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 6 7
1 2
1 3
2 3
3 5
4 5
4 6
6 5
| 4
3 1
5 1
5 4
5 4

|
h3. Explicatie

...

!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