== 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:
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.
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.
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 - 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.
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 vor afla N numere reprezentand culorile asociate fiecarui nod.
h2. Restricţii
* $1 ≤ N, M ≤ 100.000$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. something.in |_. something.out |
| 3 3
1 2
2 3
3 1
| 1 2 3
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="something") ==
