Să considerăm un poligon convex cu N vârfuri, numerotate în ordinea acelor de ceasornic de la 1 la N. O diagonală în poligon uneşte două vârfuri neadiacente. Poligonul fiind convex, orice diagonală este inclusă în interiorul poligonului.
Poligonul este partiţionat în triunghiuri prin N-3 diagonale care nu se intersectează.

Cerinţă

Să se coloreze laturile poligonului şi cele N-3 diagonale în roşu sau negru, astfel încât fiecare triunghi să aibă atât laturi roşii, cât şi laturi negre.

Date de intrare

Fişierul de intrare colorare.in conţine pe prima linie numărul natural N. Pe următoarele N-3 linii sunt descrise cele N-3 diagonale, câte o diagonală pe o linie. O diagonală este specificată prin două numere x y, cuprinse între 1 şi N, reprezentând cele două vârfuri neadiacente unite de diagonala respectivă.

Date de ieşire

Fişierul de ieşire colorare.out va conţine 2N-3 linii, câte una pentru fiecare dintre cele N laturi şi cele N-3 diagonale. Pe fiecare linie sunt scrise 3 valori x y c, unde x şi y sunt cele două vârfuri unite de latura/diagonală, iar c este culoarea în care a fost colorat latura/diagonala [x,y] (1 pentru roşu, 2 pentru negru).

Restricţii

• 4 ≤ N ≤ 100

Exemple

colorare.in	colorare.out
4 1 3	1 2 1 1 3 2 1 4 1 2 3 1 3 4 1

prof. Emanuela Cerchez

Liceul de Informatică „Grigore Moisil” Iaşi

emanuela.cerchez@gmail.com