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

Poveste şi cerinţă...

Se da un graf orientat cu $N$ noduri si $M$ muchii. Prin a reorienta o muchie se intelege ca daca in graf exista muchia $(a, b)$ (adica muchie de la nodul $a$ spre nodul $b$), o poate sterge si plasa in locul ei muchia $(b, a)$ (de la nodul $b$ spre nodul $a$).
De asemenea, prin notiunea de ciclu intr-un graf se intelege o secventa de noduri $(v~1~, v~2~, ..., v~k~)$, cu proprietatea ca pentru orice $i ≤ k-1$ in graf exista muchie de la nodul $v~i~$ spre nodul $v~i+1~$, si de asemenea exista muchie de la nodul $v~k~$ spre nodul $v~1~$.
 
h2. Cerinta
 
Reorientati un numar minim de muchii din graful dat, astfel incat acesta sa contina cel putin un ciclu. Se garanteaza ca exista un numar de muchii (eventual $0$) ce pot fi reorientate astfel incat sa se formeze ciclu.

h2. Date de intrare

Fişierul de intrare $orient.in$ ...

Fişierul de intrare $orient.in$ contine pe prima linie doua numere naturale $N$ si $M$, separate prin cate un spatiu, reprezentand numarul de noduri, respectiv numarul de muchii ale grafului. Urmatoarele $M$ linii contin fiecare cate doua numere naturale distincte $a$ si $b$, separate prin cate un spatiu, cu proprietatea ca in graf exista o muchie orientata de la nodul $a$ spre nodul $b$.

h2. Date de ieşire

În fişierul de ieşire $orient.out$ ...

În fişierul de ieşire $orient.out$ se va gasi pe prima linie un singur numar natural, reprezentand numarul minim de muchii care trebuie reorientate pentru a forma un ciclu.

h2. Restricţii

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

* $2 ≤ N ≤ 2000$
* $2 ≤ M ≤ 5000$
* Daca graful contine deja un ciclu, raspunsul problemei va fi $0$.
* Un ciclu nu trebuie neaparat sa contina toate cele $N$ noduri ale grafului. Un ciclu poate contine minim $2$ noduri.

h2. Exemplu
table(example). |_. orient.in |_. orient.out |

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

| 5 5
  1 2
  3 2
  3 4
  4 1
  4 5
| 1

|
h3. Explicaţie

...

Putem reorienta muchia $(3 2)$, obtinand astfel ciclul: $(1, 2, 3, 4)$.

== include(page="template/taskfooter" task_id="orient") ==