Revizia anterioară Revizia următoare
| 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 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.
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.
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 |
