Fişierul intrare/ieşire:3color.in, 3color.outSursăAlgoritmiada 2014, Runda 1
AutorCosmin Silvestru NegruseriAdăugată dea_h1926Heidelbacher Andrei a_h1926
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

3color

Numim o colorare a unui graf neorientat o mulţime de culori asociată nodurilor, astfel încat oricare două noduri adiacente să aibă culori diferite. Numim un graf k-colorabil dacă există o colorare a grafului care conţine cel mult k culori distincte.
Se dă un graf neorientat cu V noduri numerotate de la 0 la V - 1 şi E muchii care este 3-colorabil. Vi se cere să găsiţi o 100-colorare a acestuia.

Date de intrare

Fişierul de intrare 3color.in conţine pe prima linie numerele întregi V şi E cu semnificaţia din enunţ. Pe următoarele E linii se vor afla câte două numere întregi x şi y reprezentând o muchie de la nodul x la nodul y.

Date de ieşire

În fişierul de ieşire 3color.out veţi afişa V numere cuprinse între 0 şi 99, semnificand culorile asociate nodurilor.

Restricţii

  • 1 ≤ V ≤ 1000
  • 1 ≤ E ≤ 15.000
  • dacă există mai multe soluţii, puteţi afişa oricare.

Exemplu

3color.in3color.out
6 9
0 1
0 2
0 4
0 5
0 3
1 2
2 5
2 3
2 4
0 1 2 3 4 5

Explicaţie

Putem asocia cîte o culoare diferită fiecarui nod.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?