Zăhărel a devenit primar în oraşul său, iar prima masură pe care o va lua va fi dezvoltarea turismului. În oraş există N obiective turistice legate între ele prin M străzi cu sens unic. Pentru a atrage cât mai mulţi turişti în oraşul său trebuie să existe posibilitatea formării unui traseu turistic astfel: se pleacă de lângă un obiectiv turistic, se parcurge fiecare stradă exact o dată şi se revine în locul din care s-a plecat. (Ideal ar fi să se poată construi un traseu care sa viziteze fiecare obiectiv turistic doar o dată, nu fiecare stradă, dar această problemă este prea grea :).
Cerinţă
Scrieţi un program pentru Zăhărel care să determine numărul minim de străzi suplimentare care trebuie construite în oraş astfel încât să existe posibilitatea formării unui traseu turistic.
Date de intrare
Fişierul de intrare turism.in conţine pe prima linie numerele naturale N şi M. Următoarele M linii conţin perechi de numere întregi a b separate prin spaţii cu semnificaţia că există un o stradă cu sens unic de la obiectivul turistic a la obiectivul turistic b.
Date de ieşire
Fişierul de ieşire turism.out va conţine pe prima linie un singur număr întreg K reprezentând numărul minim de străzi suplimentare care trebuie construite în oraş astfel încât să existe posibilitatea formării unui traseu turistic. Următoarele K linii conţin perechi de numere întregi a b separate prin spaţii cu semnificaţia că se va construi o stradă cu sens unic de la obiectivul turistic a la obiectivul turistic b.
Restricţii
1 ≤ N ≤ 30 000
0 ≤ M ≤ 100 000
Obiectivele turistice sunt numerotate cu numere întregi de la 1 la N
Pot exista mai multe străzi cu sens unic între două obiective
Pentru un test se va acorda 30% din punctaj dacă se determină corect numărul K de străzi suplimentare, 70% din punctaj dacă se determină şi un set de K străzi care respectă condiţiile din enunţ, respectiv 100% din punctaj dacă setul de K muchii este minim din punct de vedere lexicografic
Un set de străzi S1=(a1,b1)(a2,b2)…(aK,bK) este mai mic din punct de vedere lexicografic decât alt set de străzi S2=( c1,d1)( c2,d2)…( cK,dK) dacă există o poziţie 1≤p≤K astfel încât ap<cp sau ap=cp şi bp<dp, iar (ai,bi)=( ci,di) pentru 1≤i<p
Exemple
turism.in
turism.out
Explicaţii
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
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)
