Se dă un graf orientat fără circuite cu n noduri (numerotate de la 1 la n) şi m arce.
Un drum în graf este o succesiune de unul sau mai multe vârfuri D=(x1, x2, ..., xk) astfel încât pentru orice 1<=i<k, există arcul (xi, xi+1).
Numim acoperire a grafului o mulţime de drumuri din graf, cu proprietatea că fiecare vârf al grafului aparţine cel puţin unui drum din mulţime.
Nu este necesar ca drumurile dintr-o acoperire să fie disjuncte (nici relativ la vârfuri, nici relativ la arce).
Cerinţă
Determinaţi numărul minim de drumuri cu care se poate acoperi un graf dat.
Date de intrare
În fişierul de intrare drumuri.in se află pe prima linie numerele naturale n şi m, separate printr-un spaţiu.
Pe fiecare dintre următoarele m linii se găseşte câte o pereche de numere naturale i, j (1 <= i, j <= n) separate printr-un spaţiu, cu semnificaţia că există arc de la vârful i la vârful j.
Date de ieşire
Fişierul de ieşire drumuri.out va conţine o singură linie reprezentând numărul minim de drumuri cu care se poate acoperi graful din fişierul de intrare.