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

Se numeste *graf bipartit* un graf $G$ ale carui noduri pot fi partitionate in doua multimi dijscunte $A$ si $B$ astfel incat oricare muchie contecteaza un nod din $A$ si un nod din $B$. Cu alte cuvinte, nu exista doua nudori $i$ si $j$ din aceeasi multime astfel incat sa existe muchie intre ele.

h3. Definitie
 
Se numeste *graf bipartit* un graf $G$ ale carui noduri pot fi partitionate in doua multimi dijscunte $A$ si $B$ care au umratoarele proprietati:
 
# ∀ $i$, $j$ ∈ $A$ nu exista muchie intre $i$ si $j$
# ∀ $i$, $j$ ∈ $B$ nu exista muchie intre $i$ si $j$
# ∀ $i$ ∈ $A$ ∃ $j$ ∈ $B$ astfel incat intre $i$ si $j$ sa fie muchie
 
h3. Problema

Fie $G$ un graf bipartit. Numim *cuplaj* o submultime de noduri <tex>M \subset A</tex> cu proprietatea ca &forall; $i$ &isin; $M$ exista un unic $j$ &isin; $B$ astfel incat intre $i$ si $j$ sa fie muchie. Numim *cuplaj maxim* o multime $M$ de cardinal maxim, adica nu exista nico alta multime $M'$ cu $|M'| &gt; |M|$ (unde cu $|M|$ am notat cardinalul multimii $M$).

h2. Restrictii
* $1 ≤ N1, N2 ≤ 1000$

* $1 ≤ M ≤ 200 000$

* $1 ≤ M ≤ (N1+N2)*(N1+N2-1)/2$

* nodurile multimii $A$ sunt numerotate de la $1$ la $N1$
* nodurile multimii $B$ sunt numerotate de la $1$ la $N2$