ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Junior Contest, October 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

K. Kerchiefs

Time limit: 2.0 second
Memory limit: 64 MB
The French Empress Josephine was proud of her collection of triangular kerchiefs. But one day she was completely upset when she found out that her collection had been stolen. What's more, this happened just a few hours before the arrival of the Austrian Emperor's delegation. Josephine couldn't confess that she was powerless against thieves, so she decided to make new kerchiefs herself.
Josephine took a piece of cloth in the form of a regular N-gon and numbered its vertices from 1 to N in the counter-clockwise order. She decided to cut the cloth into triangles along some of the N-gon's diagonals in such a way that no two cuts intersect. The empress made K cuts and hesitated. She didn't know how to continue. Can you help the French Empress?

Input

The first line contains the number of the N-gon's vertices N (3 ≤ N ≤ 50000). In the second line, there is the integer K (0 ≤ K ≤ N − 3). Each of the next K lines contains two integers A and B (1 ≤ AB ≤ N); they are the numbers of vertices between which a cut has been made (of course, these vertices are not adjacent). It is guaranteed that the cuts do not intersect.

Output

In the first line, output the number P of additional cuts needed to cut the cloth into triangles. In the next P lines, output these cuts in the same format as in the input. If there are several ways to cut the cloth, you may output any of them.

Sample

inputoutput
5
1
1 4
1
3 1
Problem Author: Alex Samsonov
Problem Source: XIII-th USU Junior Contest, October 2006
To submit the solution for this problem go to the Problem set: 1499. Kerchiefs