Bipartició oculta P30564

Recordeu que un graf és bipartit si podem partir el conjunt de vèrtexs en dos subconjunts $A$ i $B$ (algun pot ser buit) de manera que cada aresta connecti un vèrtex d’$A$ amb un de $B$.

Donat un graf no dirigit amb $n$ vèrtexs i $m$ arestes, digueu si es pot fer bipartit eliminant com a màxim $\frac{m}{2}$ arestes. En cas afirmatiu, doneu un possible conjunt d’arestes a eliminar.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $n$ i $m$, seguits d’$m$ parells $x$ $y$ indicant una aresta entre $x$ i $y$, amb $x \ne y$. Els vèrtexs del graf es numeren entre 0 i $n - 1$. No hi ha arestes repetides. Assumiu que $n$ i $m$ estan entre 1 i $10^5$.

Sortida

Escriviu una línia per cada cas. Si no és possible eliminar com a molt $k$ arestes per obtenir un graf bipartit, amb $k \le \frac{m}{2}$, escriviu només el nombre -1. Altrament, escriviu primer $k$, seguida de les $k$ arestes a eliminar (totes diferents). Podeu escriure en qualsevol ordre tant les arestes entre si com els dos vèrtexs de cada aresta. Cada aresta ha d’anar precedida de dos espais. Seguiu estrictament el format dels exemples. Si hi ha més d’una solució possible, escriviu la que vulgueu.