| Fişierul intrare/ieşire: | something.in, something.out | Sursă | FMI No Stress 5 |
| Autor | Mihai Calancea | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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 C1 si C2 se poate ajunge din orice nod colorat cu C1 în orice nod colorat cu C2 fără a trece prin noduri colorate cu C3.
3) Există cel puţin un nod de fiecare culoare.
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.
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ă.
Restricţii
- 1 ≤ N, M ≤ 100.000
Exemplu
| something.in | something.out |
|---|---|
| 3 3 1 2 2 3 3 1 | 1 2 3 |
