Московская городская олимпиада школьников по информатике,
2004/05 учебный год
при поддержке компании
Задача G. Разноцветные треугольники
| Имя входного файла: | g.in |
| Имя выходного файла: | g.out |
| Максимальное время работы на одном тесте: | 3 секунды |
| Максимальный объем используемой памяти: | 16 мегабайт |
Выпуклый N-угольник разбит непересекающимися диагоналями на треугольники. (Многоугольник называется выпуклым, если любая его диагональ лежит внутри него.) Требуется покрасить каждую сторону и каждую проведенную диагональ в красный или синий цвет так, чтобы у каждого треугольника были стороны как красного, так и синего цвета.
Требуется привести любую из допустимых раскрасок.
Формат входных данных
В первой строке записано одно число N (4≤N≤100) - количество вершин многоугольника.
Далее следуют N-3 строки, в каждой из которых записана пара натуральных чисел - номера вершин, которые соединяет диагональ. Считается, что все вершины занумерованы последовательно натуральными числами от 1 до N.
Формат выходных данных
В выходном файле должны быть 2N-3 строки. Каждая строка содержит 3 числа: номера вершин, которые соединяет данная сторона или диагональ и цвет (1 - синий, 2 - красный), в который Вы красите данную сторону или диагональ.
Примеры
| g.in | g.out |
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 |