Road Construction

Description:

Input:

The first line consists of two integers n and m .

Then m lines follow, each consisting of two integers a_i and b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i), which means that it is not possible to construct a road connecting cities a_i and b_i. Consider the cities are numbered from 1 to n.

It is guaranteed that every pair of cities will appear at most once in the input.

Output:

You should print an integer s: the minimum number of roads that should be constructed, in the first line. Then s lines should follow, each consisting of two integers a_i and b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i), which means that a road should be constructed between cities a_i and b_i.

If there are several solutions, you may print any of them.

Sample Input:

4 1
1 3

Sample Output:

3
1 2
4 2
2 3

Note:

This is one possible solution of the example:

These are examples of wrong solutions:

The above solution is wrong because it doesn't use the minimum number of edges (4 vs 3). In addition, it also tries to construct a road between cities 1 and 3, while the input specifies that it is not allowed to construct a road between the pair. The above solution is wrong because you need to traverse at least 3 roads to go from city 1 to city 3, whereas in your country it must be possible to go from any city to another by traversing at most 2 roads. Finally, the above solution is wrong because it must be possible to go from any city to another, whereas it is not possible in this country to go from city 1 to 3, 2 to 3, and 4 to 3.