== include(page="template/taskheader" task_id="something") ==

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:

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 {c1,c2,c3} 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 oraş colorat cu $C_1$ în orice oraş colorat cu $C_2$ fără a trece prin oraşe colorate cu $C_3$.

2) Pentru oricare două culori C1 si C2 se poate ajunge din orice oraş colorat cu C1 în orice oraş colorat cu C2 fără a trece prin oraşe colorate cu C3.

h2. Date de intrare

Fişierul de intrare $something.in$ are pe prima linie $N$ - numărul de noduri, $M$ numărul de muchii. Pe următoarele $M$ linii se află câte $2$ numere $x$ $y$ separate prin câte un spaţiu seminificând că există muchie între nodurile $x$ şi $y$.

Fişierul de intrare $something.in$ are pe prima linie N - numărul de noduri, M numărul de muchii. Pe următoarele M linii se află câte 2 numere x y separate prin câte un spaţiu seminifcând că există muchie între nodurile x şi y.

h2. Date de ieşire

În fişierul de ieşire $something.out$ se va afla numărul $-1$ dacă o colorare după regulile de mai sus nu este posibilă pe graful dat. Altfel, se vor afla $N$ numere din mulţimea ${1,2,3}$ separate prin câte un spaţiu, al $i$-lea din aceste numere semnificând culoarea celui de-al $i$-lea nod. Se acceptă orice soluţie corectă.

În fişierul de ieşire $something.out$ se va afla numărul -1 dacă o colorare după regulile de mai sus nu este posibilă pe graful dat. Altfel, se vor afla N numere din mulţimea {1,2,3} separate prin câte un spaţiu, al i-lea din aceste numere semnificând culoarea celui de-al i-lea nod. Se acceptă orice soluţie corectă.

h2. Restricţii