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

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

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 fişierului $color5.in se va afla un singur număr natural $N$ avînd semnificaţia din enunţ.

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

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

h2. Restricţii