something

Something

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

Se da un graf neorientat G, cu N noduri si M muchii. Se cere sa determinati o colorare a acestui graf folosind 3 culori din multimea {c1,c2,c3} astfel incat:
1)Daca ne uitam separat pe culori, fiecare graf e conex (se iau in considerare doar muchiile intre noduri de culoarea respectiva).
2)Pentru oricare doua culori C1 si C2 se poate ajunge din orice oras colorat cu C1 in orice oras colorat cu C2 fara a trece prin orase colorate cu C3.

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~}$.
3) Există cel puţin un nod de fiecare culoare.

h2. Date de intrare

Fişierul de intrare $something.in$ are pe prima linie N - numarul de noduri, M numarul de muchii. Pe urmatoarele M linii se afla cate 2 numere x y separate prin cate un spatiu seminifcand ca exista muchie intre nodurile x si 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 semnificând că există muchie între nodurile $x$ şi $y$.

h2. Date de ieşire

În fişierul de ieşire $something.out$ se vor afla N numere reprezentand culorile asociate fiecarui nod.

Î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$

h2. Exemplu

h3. Explicaţie

...

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

10190