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?

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 ≤ A, B ≤ 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.

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.