Fişierul intrare/ieşire:circle.in, circle.outSursăShumen 2019 Seniori
AutorAdăugată deMatteoalexandruMatteo Verzotti Matteoalexandru
Timp execuţie pe test1.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Circle

Intr-un sat se afla N case intr-o ordine circulara. Casele sunt numerotate in ordinea acelor de ceasornic cu numere de la 1 la N. De exemplu, daca N = 8, atunci satul ar arata in felul urmator:

De asemenea, in sat se afla M strazi, fiecare conecteaza doua case si se afla in interiorul cercului. De asemenea, strazile nu se intersecteaza intre ele, dar capetele lor pot fi aceleasi. Deoarece se apropie un festival, satenii vor sa isi zugraveasca locuintele. Din pacate, acest lucru nu este foarte simplu, deoarece acestia nu vor sa aiba strazi plictisitoare in satul lor. Ei considera o strada a fi plictisitoare daca locuintele de la capetele strazii au aceeasi culoare.

Acum este randul tau! Deoarece vopseaua este scumpa, satenii vor sa foloseasca un numar minim de culori. Ajuta-i prin a scrie un program care gaseste numarul minim de culori necesare si care gaseste un mod convenabil de a zugravi casele.

Date de intrare

Fişierul de intrare circle.in contine pe prima linie numerele naturale N si M - numarul de case si numarul de strazi din sat. Fiecare din urmatoarele M linii contine doua numere u si v - acestea semnifica faptul ca exista o strada intre casele cu numerele u si v.

Date de ieşire

În fişierul de ieşire circle.out va contine pe prima linie numarul K - numarul minim de culori necesare. Pe urmatoarea linie se vor afla N numere - culorile in care trebuie pictata fiecare casa. Culorile sunt numerotate de la 1 la K. Daca sunt mai multe raspunsuri corecte, puteti afisa oricare dintre ele.

Restricţii

  • 2 ≤ N ≤ 5 * 105
  • 1 ≤ M ≤ 5 * 105

Exemplu

circle.incircle.out
6 5
1 2
2 3
1 4
3 4
6 5
2
1 2 1 2 1 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?