Circulatie

circulatie

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

Se numeste graf bipartit un graf ale carui noduri pot fi partitionate in $2$ multimi astfel incat orice muchie are capetele in multimi distincte. In aceasta problema vom considera ca graful este deja partitionat, ambele multimi avand noduri numerotate de la $1$ la $N$. Fie un asemenea graf bipartit cu $2 * N$ noduri unde fiecare nod are gradul $3$ (este conectat cu alte $3$ noduri). Marele Intelept iti da urmatoarea sarcina. Tu trebuie sa orientezi muchiile grafului si sa le atribui costuri naturale cuprinse in intervalul $[1, 3]$ astfel incat pentru orice nod, suma costurilor muchiilor care intra in nod sa fie egala cu suma costurilor muchiilor care ies din nod.
 
Orice solutie este acceptata.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $circulatie.in$ va contine pe prima linie numarul natural $N$ reprezentand numarul de noduri din graf. Pe urmatoarele $3 * N$ linii vor fi cate $2$ numere naturale $a$ si $b$ reprezentand faptul ca exista muchie de la nodul $a$ din prima multime la nodul $b$ din a doua multime.

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

h2. Date de ieşire

Fişierul de ieşire $circulatie.out$ va contine $3 * N$ linii de forma $a b c$, semnificand faptul ca muchia $a - b$ ( $a$ din prima multime si $b$ din a doua multime) va avea costul $c$. Daca orientarea muchiei este $a -> b$, $c$ va fi pozitiv. Altfel, $c$ va fi negativ.

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

h2. Restricţii

* $3 ≤ N ≤ 10^5^$

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

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

| 3
1 1
1 2
2 3
3 1
2 2
1 3
3 2
3 3
2 1
| 1 2 -2
2 3 -3
2 2 1
3 2 1
1 1 1
1 3 1
2 1 2
3 1 -3
3 3 2

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

|

h3. Explicaţie
 
...
 

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