Fişierul intrare/ieşire:something.in, something.outSursăFMI No Stress 5
AutorMihai CalanceaAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.4 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.insomething.out
3 3
1 2
2 3
3 1
1 2 3

Explicaţie

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content