== include(page="template/taskheader" task_id="harti") ==
Lorena, surioara Mirunei, a învăţat recent la cercul de informatică că orice hartă poate fi colorată folosind maxim patru culori. Cum fetiţa nu s-a lăsat convinsă în lipsa unei demonstraţii ea a petrecut ultimele două săptămâni încercând să găsească un contraexemplu. Într-un final, plictisită de atâta muncă fără rezultate, a decis ca se va mulţumii cu a demonstra proprietatea pe un caz mult mai particular. Astfel s-a născut următoarea problemă:

Fie un graf cu noduri de forma $(x{~i~}, y{~i~})$ în care oricare două muchii nu se intersectează decât, eventual, într-unul dintre capete. Orice muchie $u-v$ respectă una dintre următoarele condiţii:

Fie un graf planar cu noduri de forma $(x{~i~}, y{~i~}$ în care orice muchie $u-v$ respectă una dintre următoarele condiţii:

* $x{~v~} = x{~u~}$
* $y{~v~} = y{~u~}$
* $|x{~v~} - x{~u~}| = |y{~v~} - y{~u~}|$

!problema/harti?harti1.png 200x200! !problema/harti?harti2.png 215x215!

!problema/harti?harti1.png 200x200! !problema/harti?harti2.png 200x200!

Găsiţi o colorare a nodurilor grafului, care foloseşte maxim $K$ culori, astfel încât să nu existe două noduri cu aceeaşi culoare conectate print-o muchie.

h2. Restricţii

* $1 ≤ N ≤ 2 000$
* $1 ≤ M ≤ 5 000$
* $0 ≤ x{~i~}, y{~i~} ≤ 1 000$, pentru orice $1 ≤ i ≤ N$
* $1 ≤ u{~i~}, v{~i~} ≤ N$, pentru orice $1 ≤ i ≤ M$

* $1 ≤ N ≤ 10 000$
* $1 ≤ M ≤ 10 000$
* $0 ≤ x{~i~}, y{~i~} ≤ 1000$, pentru orice $1 ≤ i ≤ N$
* $0 ≤ u{~i~}, v{~i~} ≤ N$, pentru orice $1 ≤ i ≤ M$

* $u{~i~} ≠ v{~i~}$, pentru orice $1 ≤ i ≤ M$
* Nodurile sunt distincte două câte două.
* Muchiile sunt distincte două câte două (nu există muchii duble).
* Nu există muchie de la un nod la el însuşi.

* Se garanteaza ca exista solutie.

h2. Subtaskuri