== 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 nod colorat cu $C{~1~}$ în orice nod colorat cu $C{~2~}$ fără a trece prin noduri colorate cu $C{~3~}$.
3) Există cel puţin un nod de fiecare culoare.
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 semnificâ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
* $1 ≤ N, M ≤ 100.000$
* $1 ≤ N,M ≤ 100.000$
h2. Exemplu
