Determinati numarul minim de drumuri cu care se poate acoperi un graf dat.

h2. Date de Intrare

h2. Date de intrare

In fisierul de intrare $drumuri.in$ se afla pe prima linie numerele naturale $N$ si {$M$}, separate printr-un spatiu.

In fisierul de intrare $drumuri2.in$ se afla pe prima linie numerele naturale $N$ si {$M$}, separate printr-un spatiu.

Pe fiecare dintre urmatoarele $M$ linii se gaseste cate o pereche de numere naturale {$i$}, $j$ $(1 ≤ i, j ≤ N)$ separate printr-un spatiu, cu semnificatia ca exista arc de la varful $i$ la varful {$j$}.

h2. Date de Iesire

h2. Date de iesire

Fisierul de iesire $drumuri.out$ va contine o singura linie reprezentand numarul minim de drumuri cu care se poate acoperi graful din fisierul de intrare.

Fisierul de iesire $drumuri2.out$ va contine o singura linie reprezentand numarul minim de drumuri cu care se poate acoperi graful din fisierul de intrare.

h2. Restrictii

h2. Exemplu

table(example). |_. drumuri.in |_. drumuri.out |_. Explicatie |

table(example). |_. drumuri2.in |_. drumuri2.out |

| 7 7
1 2
7 2

3 5
4 5
4 6

| 2
| D1 : 1->2->3->5
D2 : 7->2->4->6 |

| 2 |
 
h3. Explicatii
 
$D1: 1->2->3->5$
$D2: 7->2->4->6$

==Include(page="template/taskfooter" task_id="drumuri2")==

1093