== include(page="template/taskheader" task_id="circle") ==

Poveste şi cerinţă...

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:
 
!problema/circle?circle.png!
 
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.

h2. Date de intrare

Fişierul de intrare $circle.in$ ...

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$.

h2. Date de ieşire

În fişierul de ieşire $circle.out$ ...

Î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.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 5 * 10^5^$
* $1 ≤ M ≤ 5 * 10^5^$

h2. Exemplu
table(example). |_. circle.in |_. circle.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 6 5
1 2
2 3
1 4
3 4
6 5
| 2
1 2 1 2 1 2

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="circle") ==