Имеется выпуклый многоугольник, вершины которого окрашены в три цвета: красный (R), зеленый (G), либо голубой (B). При этом известно, что все три цвета точно присутствуют и никакие две соседние вершины не окрашены одинаково. Требуется выяснить, можно ли разрезать этот многоугольник непересекающимися диагоналями на треугольники так, чтобы у всех полученных треугольников была бы одна красная вершина, одна зелёная и одна голубая. Если это возможно, то требуется также указать возможный вариант разрезания.
Исходные данные
В первой строке содержится количество вершин многоугольника N (не менее 4 и не более 1000). Во второй строке находятся N символов из набора {R, G, B}, каждый из которых описывает раскраску цвет вершины многоугольника (в порядке обхода).
Результат
В первой строке должно содержаться количество проведённых диагоналей, если требуемое разрезание возможно, либо число 0, если разрезание невозможно. В случае, когда разрезание возможно, в следующих строках должно содержаться описание диагоналей, по которым проводится разрез. Описание одной диагонали занимает одну строку и состоит из пары номеров вершин, которые соединяет данная диагональ, разделенных пробелом. Если для данного многоугольника существует несколько вариантов разрезания, удовлетворяющих условиям, то достаточно указать любой из них.
Пример
исходные данные | результат |
---|
7
RBGBRGB
| 4
1 3
3 7
5 7
5 3
|
Автор задачи: Дмитрий Филимоненков
Источник задачи: Third USU personal programming contest, Ekaterinburg, Russia, February 16, 2002