== 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 planar cu noduri de forma $(x{~i~}, y{~i~})$ în care orice muchie $u-v$ respectă una dintre următoarele condiţii:

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:

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

h2. Restricţii

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

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

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