harti

Hărți

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

Poveste şi cerinţă...

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~}|$
 
!problema/harti?harti1.png 200x200! !problema/harti?harti2.png 215x215!
 
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. Date de intrare

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

Fişierul de intrare $harti.in$ va avea următorul format:
$N M K$
$x{~1~} y{~1~}$
$x{~2~} y{~2~}$
$...$
$x{~N~} y{~N~}$
$u{~1~} v{~1~}$
$...$
$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~}$.

h2. Date de ieşire

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

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

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$
* $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
 
table(subtask-uri). |_. Indice |_. Punctaj |_. Restricţii |
| $1$ | $10$ puncte | $K = 9$ |
| $2$ | $15$ puncte | $K = 6$ |
| $3$ | $25$ puncte | $K = 5$ |
| $4$ | $50$ puncte | $K = 4$ |

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

| 5 8 4
  0 2
  2 2
  0 0
  1 1
  2 0
  1 2
  1 3
  1 4
  2 4
  2 5
  3 4
  3 5
  4 5
| 1
  2
  2
  3
  1
|
| 6 10 5
  0 2
  1 2
  1 1
  2 1
  0 0
  1 0
  1 2
  1 3
  1 5
  2 3
  2 4
  3 4
  5 6
  5 3
  6 3
  6 4
| 1
  2
  3
  4
  2
  1
|

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