color

Cerință

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 \cdot N$.

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.

Date de intrare

Pe prima line a fișierului color.in se va afla un singur număr natural $N$ având semnificaţia din enunț.

Date de ieșire

În fișierul color.out se va afișa pe prima linie un singur număr natural $M$ reprezentând numărul de culori folosit. Următoarele $2 \cdot 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$.

Restricții și precizări

• $3 \leq N \leq 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 fiecare test va fi calculat folosind formula: $\displaystyle \left( \frac{raspuns_{optim}}{raspuns_{concurent}} \right) ^2 \cdot 10$

Exemplu

color.in

3

color.out

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

Explicație

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