Màxim nombre de vèrtexs vermells P24562

Feu un programa que, donat un graf no dirigit, digui si és possible pintar-ne tots els vèrtexs només amb dos colors (vermell i blau), de manera que no hi hagi dos vèrtexs veïns del mateix color. En cas afirmatiu, cal maximitzar el nombre de vèrtexs de color vermell.

Entrada

L’entrada consisteix en diversos casos, cadascun amb el nombre de vèrtexs n i el nombre d’arestes m, seguits d’m parells x y indicant una aresta entre x i y. Suposeu 1 ≤ n ≤ 10⁴, 0 ≤ m ≤ 5n, que els vèrtexs es numeren entre 0 i n − 1, x ≠ y, i que no hi ha més d’una aresta entre cada parell x y.

Sortida

Per a cada cas, si el graf es pot pintar amb els dos colors, escriviu “yes” seguit del màxim nombre possible de vèrtexs vermells. Altrament, escriviu “no”.