|
Выпуклый N-угольник разбит непересекающимися диагоналями на треугольники. (Многоугольник называется выпуклым, если любая его диагональ лежит внутри него.) Требуется покрасить каждую сторону и каждую проведенную диагональ в красный или синий цвет так, чтобы у каждого треугольника были стороны как красного, так и синего цвета.
Требуется привести любую из допустимых раскрасок.
Формат входных данных
В первой строке записано одно число N (4≤N≤100) - количество вершин многоугольника.
Далее следуют N-3 строки, в каждой из которых записана пара натуральных чисел - номера вершин, которые соединяет диагональ. Считается, что все вершины занумерованы последовательно натуральными числами от 1 до N.
Формат выходных данных
В выходном файле должны быть 2N-3 строки. Каждая строка содержит 3 числа: номера вершин, которые соединяет данная сторона или диагональ и цвет (1 - синий, 2 - красный), в который Вы красите данную сторону или диагональ.
Примеры
| input |
output |
4
1 3 |
1 2 1
2 3 1
3 4 1
4 1 1
1 3 2 |
6
1 3
3 5
5 1 |
1 2 1
2 3 1
3 4 1
3 5 2
4 5 1
5 6 2
5 1 1
6 1 2
1 3 2 |
|
