Color5

color5

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

Se dă un graf cu $N + 1$ noduri numerotate de la $0$ la $N$. Există muchii de la nodul $N$ la toate celelalte $N$ noduri şi între oricare două noduri $A$ şi $B$ cu proprietatea că $A, B < N$ şi $(A + 1) = B$ mod $N$. Se observă că numărul total de muchii este $2 * N$.
 
h2. Cerinţă
 
Se cere să coloraţi muchiile grafului cu un număr cît mai mic de culori astfel încît între oricare două noduri să existe cel puţin un drum care conţine doar muchii colorate distinct.

Se da un graf cu $N + 1$ numerotate de la $0$ la $N$. Exista muchii de la nodul $N$ la toate celelalte $N$ noduri si intre oricare doua noduri $A$ si $B$ cu proprietatea ca $A, B$ &l; $N$ si $(A + 1) = B$ mod $N$. Se observa cu numarul total de muchii este $2 * N$.

h2. Date de intrare

Pe prima linie a fişierului $color5.in$ se va afla un singur număr natural $N$ avînd semnificaţia din enunţ.

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

h2. Date de ieşire

În fişierul $color5.out$ se va afişa pe prima linie un singur număr natural $M$ reprezentînd numărul de culori folosite. Următoarele $2 * N$ linii vor conţine cîte trei numere $A$, $B$ şi $C$, semnificînd faptul că muchia dintre nodurile $A$ şi $B$ a fost colorată în culoarea $C$.

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

h2. Restricţii

* $3 ≤ N ≤ 100$
* Culorile afişate în fişierul de ieşire trebuie să fie numere naturale din intervalul $[1, M]$, unde $M$ este numărul de culori folosite.
* Scorul pe care îl veţi obţine pe ficare test va fi calculat folosind formula: [(Răspuns_optim / Răspuns_concurent)^2^ * 10)].

* $... ≤ ... ≤ ...$
1 ≤ 5
a{~i~}

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

|3
| 1
  0 3 1
  1 3 1
  2 3 1
  0 1 1
  1 2 1
  2 0 1

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

|
h3. Explicaţie

Avem muchie între oricare două noduri, deci putem folosi o singură culoare pentru colorarea grafului.

...

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