Fişierul intrare/ieşire:	harti.in, harti.out	Sursă	ad-hoc
Autor		Adăugată de	Livia Magureanu •livlivi
Timp execuţie pe test	0.2 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Hărți

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:

• x_v = x_u
• y_v = y_u
• |x_v - x_u| = |y_v - y_u|

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.

Date de intrare

Fişierul de intrare harti.in va avea următorul format:
N M K
x₁ y₁
x₂ y₂
...
x_N y_N
u₁ v₁
...
u_M v_M

Pe prima linie se află trei numere, N, M şi K, reprezentând numărul de noduri, numărul de muchii şi, respectiv, numărul culorilor disponibile.
Nodurile sunt numerotate de la 1 la N.
Pe următoarele N linii vor fi câte două numere, x_i şi y_i, reprezentând coordonatele nodului i.
Pe următoarele M linii vor fi câte două numere, u_i şi v_i cu semnificaţia că există o muchie între nodurile u_i şi v_i.

Date de ieşire

În fişierul de ieşire harti.out se vor afişa N linii. Pe a i-a linie se va afla un număr cuprins între 1 şi K, culoarea nodului $$i.

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

Subtaskuri

Exemplu

Cum se trimit solutii?