Император Франции Наполеон с удивлением обнаружил, что его уникальная коллекция треуголок была похищена злоумышленниками. Причём буквально за несколько часов до прибытия делегации императора Австрии. А признаться перед августейшей особой в бессилии перед ворами Наполеон не мог. Тогда он решил сделать треуголки сам.

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

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

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