nowhere-zero

Nowhere-zero

== include(page="template/taskheader" task_id="nowhere-zero") ==

Poveste şi cerinţă...

Se dau $N$ puncte de coordonare reale in plan. Unele perechi de puncte sunt unite de catre o muchie (segment de linie dreapta). Se garanteaza ca doua astfel de muchii nu se intersecteaza (decat eventual in unul din capete). Acest sistem de puncte si muchii formeaza un graf planar. Sa se gaseasca o circulatie in acest graf, astfel incat pe orice muchie valoarea fluxului sa fie un numar intreg cuprins intre $1$ si $5$. Numim circulatie o orientare a muchiilor insotita de asocierea unei cantitati de flux pentru fiecare muchie in parte. O circulatie este considerata valida, daca pentru fiecare nod din graf fluxul care "intra" in el este egal cu fluxul care "iese" din el. Se garanteaza ca o asemenea circulatie exista pentru fiecare graf din fisierele de test.

h2. Date de intrare

Fişierul de intrare $nowhere-zero.in$ ...

Fişierul de intrare $nowhere-zero.in$ va contine pe prima linia $2$ numere naturale $N$ si $M$.
Urmatoarele $N$ linii vor avea fiecare $2$ valori *reale* cu cel mult 6 cifre după virgulă reprezentand coordonatele celui de-al $i$-lea punct.
Urmatoarele $M$ linii vor contine $2$ numere intre $1$ si $N$ distincte semnificand faptul ca exista muchie intre punctele cu acei indici.

h2. Date de ieşire

În fişierul de ieşire $nowhere-zero.out$ ...

În fişierul de ieşire $nowhere-zero.out$ se vor afisa M randuri, cate una pentru fiecare muchie din input.
Fiecare rand trebuie sa fie de forma $x y z$, $1 ≤ z ≤ 5$ cu semnificatia ca se trimit z unitati de flux de la punctul la $x$ la punctul $y$ prin muchia $(x, y)$ in aceasta directie.

h2. Restricţii

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

* $1 ≤ N ≤ 100.000$
* $-1.000.000.000 ≤ X[i], Y[i] ≤ 1.000.000.000$

h2. Exemplu
table(example). |_. nowhere-zero.in |_. nowhere-zero.out |

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

| 4 5
0 1.5
2 2
2 0
3 1
1 2
1 3
2 3
2 4
3 4
| 2 3 2
3 1 1
3 4 1
1 2 1
4 2 1

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="nowhere-zero") ==

10929