Se dă un graf neorientat conex G, cu N noduri si M muchii. Se cere sa determinaţi o colorare a acestui graf folosind 3 culori din multimea ${1,2,3}$ astfel încât:
1) Dacă ne uităm separat pe culori, fiecare graf e conex (se iau în considerare doar muchiile între noduri de culoarea respectivă).

2) Pentru oricare două culori $C{~1~}$ si $C{~2~}$ se poate ajunge din orice nod colorat cu $C{~1~}$ în orice nod colorat cu $C{~2~}$ fără a trece prin noduri colorate cu $C{~3~}$.

2) Pentru oricare două culori $C{~1~}$ si $C{~2~}$ se poate ajunge din orice oraş colorat cu $C{~1~}$ în orice oraş colorat cu $C{~2~}$ fără a trece prin oraşe colorate cu $C{~3~}$.

h2. Date de intrare