Fişierul intrare/ieşire:	turism.in, turism.out	Sursă	Lot Suceava 2007
Autor	Mircea Bogdan Pasoi	Adăugată de	Bogdan-Cristian Tataroiu •bogdan2412
Timp execuţie pe test	0.1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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 ☺).

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.

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.

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.

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 ≤ p ≤ K astfel incat ap < cp sau ap = cp si bp < dp, iar (ai,bi) = (ci,di) pentru 1 ≤ i < p.

Exemplu

Explicatie

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)

Cum se trimit solutii?