* Apare o muchie intre un nod izolat si un nod neizolat. Punem muchia. Nodul neizolat este deja colorat cu o culoare. Coloram nodul izolat cu perechea acestei culori.
* Apare o muchie intre doua noduri neizolate. Daca culorile lor coincid, afisam NO, altfel punem muchia. Sa zicem ca nodurile sunt X si Y iar culoarea lui X este a din perechea de culori (a,b) iar culoarea lui Y este c din perechea de culori (c,d). Vrem sa exprimam ca, de acum in colo, a este echivalent cu d iar b este echivalent cu c. Pentru aceasta putem folosi 'paduri de multimi disjuncte':http://www.infoarena.ro/problema/disjoint.

Complexitatea este <tex>O(N + M)</tex>.

Complexitatea este <tex>O(N + M*log^*^N)</tex> adica aproximativ <tex>O(N + M)</tex>.

==include(page="onis-2015/solutii-runda-1/perechile")==