//本题本质：已知一棵树所有节点的度数，求画出该树。 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int MAXN = 1e4 + 10;
vector<int> G[MAXN];
int n, m, sum[MAXN];

struct node {
	int deg, index;
	bool operator < (const node &a) const {
		return deg < a.deg;
	}
} a[MAXN];

int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int main() {
	n = read(); m = read();
	for (int i = 1; i <= m; i++) {
		int u = read(), v = read();
		G[u].push_back(v + 1);
		G[v].push_back(u + 1);
		a[u + 1].deg++;
		a[v + 1].deg++;
		a[u + 1].index = u + 1;
		a[v + 1].index = v + 1;
	}
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i++)
		sum[i] = sum[i - 1] + a[i].deg;
	int j = -1;
	for (int i = n; i >= 0; i--) {
		if (sum[i] + (n - i) * 1 <= 2 * (n - 1)) {
			j = i;
			break;
		}
	} 
	for (int i = 1; i <= n; i++) {
		if (i == j + 1)
			a[i].deg = 2 * (n - 1) - sum[j] - (n - j - 1);
		if (i > j + 1)
			a[i].deg = 1;
	}      
	printf("%d\n%d %d\n", n - j, n, n - 1);
	sort(a + 1, a + 1 + n);
	queue<int> q1, q2;
	for (int i = 1; i <= n; i++) {
		if (a[i].deg == 1) q1.push(i);
		else q2.push(i);
	}                    
	while (!q1.empty() && !q2.empty()) {
		int t = q1.front();
		q1.pop();
		int x = q2.front();
		printf("%d %d\n", a[t].index - 1, a[x].index - 1);
		a[x].deg--;
		if (a[x].deg == 1) {
			q2.pop();
			q1.push(x);
		}
	}
	while (!q1.empty()) {
		int t = q1.front();
		q1.pop();
		int x = q1.front();
		q1.pop();
		printf("%d %d\n", a[t].index - 1, a[x].index - 1);
	}
	return 0;   
}