== 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.*

* $3 ≤ N ≤ M ≤ 50.000$
* $Q ≤ 150.000$
* Pentru $20$ de puncte, $Q ≤ 500$

* Pentru inca $20$ de puncte, graful contine un singur ciclu
* Pentru inca $30$ de puncte, $Q ≤ 30.000$

* Pentru inca $10$ de puncte, graful contine un singur ciclu
* Pentru inca $40$ de puncte, $Q ≤ 30.000$

h2. Exemplu