ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Соревнование школьников. Октябрь 2006

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

K. Треуголки

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Император Франции Наполеон с удивлением обнаружил, что его уникальная коллекция треуголок была похищена злоумышленниками. Причём буквально за несколько часов до прибытия делегации императора Австрии. А признаться перед августейшей особой в бессилии перед ворами Наполеон не мог. Тогда он решил сделать треуголки сам.
Наполеон взял кусок ткани в форме правильного N-угольника и занумеровал его вершины числами от 1 до N в порядке обхода. Наполеон решил разрезать его на треугольники (чтобы потом свернуть их в треуголки). При этом он решил резать только по диагоналям многоугольника и так, чтобы любые два разреза не пересекались. Император взялся за дело и произвёл K разрезов. После чего он нахмурился — совершенно непонятно было, как проводить разрезы дальше. Видимо, без посторонней помощи ему не обойтись…

Исходные данные

В первой строке дано число N (3 ≤ N ≤ 50000) — количество вершин многоугольника. Во второй строке дано число K (0 ≤ K ≤ N − 3). Каждая из следующих K строк содержит пару целых чисел A и B (1 ≤ AB ≤ N) — номера вершин, между которыми уже есть разрез (эти вершины не совпадают и не являются соседними). Гарантируется, что никакие два уже сделанных разреза не пересекаются.

Результат

В первой строке выведите число P — количество дополнительных разрезов, которые необходимо сделать, чтобы разрезать кусок ткани на треугольники. В следующих P строках выведите эти разрезы в том же формате, в котором даны разрезы во входных данных. Если разрезать ткань можно несколькими способами, то выведите любой из них.

Пример

исходные данныерезультат
5
1
1 4
1
3 1
Автор задачи: Алексей Самсонов
Источник задачи: XIII командный чемпионат школьников Свердловской области по программированию (14 октября 2006 года)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1499. Треуголки