turism

Enunţ

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, parcurgându-se fiecare obiectiv turistic cel puțin o dată. (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 și precizări

• $1 \leq N \leq 30 \ 000$;
• $0 \leq M \leq 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 = (a_1, b_1)\ (a_2, b_2) \ldots (a_K, b_K)$ este mai mic din punct de vedere lexicografic decât alt
  set de străzi $S2 = (c_1, d_1)\ (c_2, d_2) \ldots (c_K, d_K)$ dacă există o poziţie $1 \leq p \leq K$ astfel încât $a_p < c_p$ sau $a_p = c_p$ şi $b_p < d_p$, iar $(a_i, b_i) = (c_i, d_i)$ pentru $1 \leq i < p$

Exemplul

turism.in

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

turism.out

4
3 1
5 1
5 4
5 4

Explicație

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)