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

Se dă un graf cu $N + 1$ 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ă cu numărul total de muchii este $2 * N$.

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 < N$ si $(A + 1) = B$ mod $N$. Se observa cu numarul total de muchii este $2 * N$.

h2. Cerintă

h2. Cerinta

Se cere să coloraţi muchiile grafului cu un număr cît mai mic de culori astfel încat între oricare două noduri să existe cel puţin un drum care conţine doar muchii colorate distinct.

Se cere sa colorati muchiile grafului cu un numar cat mai mic de culori astfel incat intre oricare doua noduri sa existe cel putin un drum care contine doar muchii colorate distinct.

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

Pe prima linie a fisierului $color5.in se va afla un singur numar natural $N$ avand semnificatia din enunt.

h2. Date de ieşire

In fisierul $color5.out$ se va afişa pe prima linie un singur număr natural $M$ reprezentînd numărul de culori folosit. 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$.

In fisierul $color5.out$ se va afisa pe prima linie un singur numar natural $M$ reprezentand numarul de culori folosit. Urmatoarele $2 * N$ linii vor contine cate trei numere $A$, $B$ si $C$, semnificand faptul ca muchia dintre nodurile $A$ si $B$ a fost colorata in culoarea $C$.

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)].

* Culorile afisate in fisierul de iesire trebuie sa fie numere naturale din intervalul $[1, M]$, unde $M$ este numarul de culori folosite.
* Scorul pe care il veti obtine pe ficare test va fi calculat folosind formula: [(Raspuns_optim / Raspuns_concurent)^2^ * 10)].

h2. Exemplu

h3. Explicaţie

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

Avem muchie intre oricare doua noduri, deci putem folosi o singura culoare pentru colorarea grafului.

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