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

Se da un graf +conex si neorientat+. Sa se taie o muchie in asa fel incat el sa devina $+_*bipartit*_+$.

Se da un graf +conex si neorientat+. Sa se taie o muchie in asa fel incat el sa devina $+_*bipartit*_+$ (conex sau nu).

h2. Date de intrare
Fişierul de intrare $bip.in$ contine, pe prima linie, numarul $T$ de teste, apoi liniile care descriu fiecare test in parte, astfel:
* pe prima linie, numerele $N$ de noduri si $M$ de muchii, despartite prin cate un spatiu

* pe urmatoarele $M$ muchii, muchiile cu indicii $0$, $1$, ..., $M-1$ descrise printr-o pereche *neordonata* de numere despartite printr-un spatiu, reprezentand nodurile

* pe urmatoarele $M$ linii, muchiile cu indicii $0$, $1$, ..., $M-1$ descrise prin cate o pereche *neordonata* de numere despartite printr-un spatiu, reprezentand nodurile

*Se garanteaza ca muchiile nu se repeta si ca, initial, graful nu e bipartit.*