ЗАДАЧА B
Триангуляция выпуклого многоугольника
| Имя входного файла: | triangle.in |
| Имя выходного файла: | triangle.out |
| Ограничение по времени: | 1 секунда |
| Ограничение по памяти: | 64 Мб |
В выпуклом N-угольнике провели несколько диагоналей таким образом, что никакие две диагонали не пересекаются внутри N-угольника.
Напишите программу, которая проверяет, разбит ли N-угольник на треугольники.
Входные данные
Во входном файле записано сначала число N - количество вершин N-угольника (3 <= N <= 1000). Далее записано число M - количество проведенных диагоналей. Далее записано M пар чисел, задающих диагонали (каждая диагональ задается парой номеров вершин, которые она соединяет). Гарантируется, что каждая пара чисел задает диагональ (то есть две вершины различны, и не являются соседними), а также что никакие две пары не задают одну и ту же диагональ. Никакие две диагонали не пересекаются внутри N-угольника.Вершины N-угольника нумеруются числами от 1 до N.
Выходные данные
Если N-угольник разбит на треугольники, то выходной файл должен содержать единственное число 0.
В противном случае быть выведено сначала число K - количество вершин в какой-нибудь не треугольной части. Далее должно быть выведено K чисел - номера вершин исходного N-угольника, которые являются вершинами этой K-угольной части в порядке обхода этой части.
Пример
| triangle.in | triangle.out |
|---|---|
|
|
|
|
|
|