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

Fie un graf orientat cu $N$ noduri si $M$ muchii. Asociem fiecarei muchii $(u,v)$ o capacitate nenegativa $cap(u,v)$. Consideram doua varfuri speciale: nodul $1$ care va fi denumit $sursa$ si nodul $N$, denumit $destinatie$. Orice nod $i$ ({$2 ≤ i ≤ N-1$}) se gaseste pe cel putin un drum de la $1$ la $N$. Definim *fluxul* in $G$ ca fiind o functie _f: V x V -> Z_, unde $V$ este multimea nodurilor grafului. Functia _f_ satisface urmatoarele conditii:

Fie un graf orientat cu $N$ noduri si $M$ muchii. Asociem fiecarei muchii $(u,v)$ o capacitate nenegativa $cap(u,v)$. Consideram doua varfuri speciale: nodul $1$ care va fi denumit $sursa$ si nodul $N$, denumit $destinatie$. Orice nod $i$ ({$2 ≤ i ≤ N-1$}) se gaseste pe cel putin un drum de la $1$ la $N$. Definim *fluxul* in graf ca fiind o functie _f: E -> Z_, unde $E$ este multimea muchiilor grafului. Functia _f_ satisface urmatoarele conditii:

# este restrictionata de capacitate, adica ∀ $i$, $j$ ∈ V avem $f(i,j) ≤ cap(i,j)$

# este antisimetrica, adica ∀ $i$, $j$ ∈ V avem $f(i,j) = -f(j,i)$

# fluxul se conserva, adica &forall; $i$ &isin; $V$ valoarea fluxului care intra in nodul respectiv este egala cu valoarea fluxlui care iese din nodul respectiv (&forall; $i$ &isin; $V$ avem ca <tex>\sum_{(i,j) \in E}^{} f(i,j) = 0</tex>, unde $E$ este multimea muchiilor grafului)

Valoarea fluxului este <tex>F = \sum_{(1,j) \in E}^{} f(1,j)</tex>, adica suma fluxlul total care pleaca din sursa.

Valoarea fluxului este <tex>F = \sum_{(i,j) \in V}^{} f(i,j)</tex>, adica suma fluxlul total care pleaca din sursa.

h2. Cerinta

Se cere sa se determine valorile functiei _f_ pentru orice muchie (i,j) astfel incat $F$ sa fie maxim.

Se cere sa se determine valorile functiei _f_ pentru fiecare muchie (i,j) astfel incat valoarea fluxului sa fie maxima.

h2. Date de intrare

h2. Restrictii
* $1 ≤ N ≤ 200$

* $1 ≤ N ≤ 19 900$

* $1 ≤ N ≤ 19900$

* capacitatea fiecarei tevi este un numar natural nenul mai mic sau egal cu $10 000 000$.
* daca in fisier exista muchia ({$a$}, {$b$}), cu siguranta nu va exista si muchia ({$b$},{$a$})
* fluxul maxim va fi ≤ $2 000 000 000$