| Fişierul intrare/ieşire: | circle.in, circle.out | Sursă | Shumen 2019 Seniori |
| Autor | Adăugată de |  Matteo Verzotti •Matteoalexandru | |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | circle.out |
|---|---|
| 6 5 1 2 2 3 1 4 3 4 6 5 | 2 1 2 1 2 1 2 |
