#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)
#define FILL(a, b) memset(a, b, sizeof(a))
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int MAX = 1 << 17;

int deg[MAX], vertices[MAX];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	while (m--) {
		int u, v;
		cin >> u >> v;
		deg[u]++;
		deg[v]++;
	}
	iota(vertices, vertices + n, 0);
	sort(vertices, vertices + n, [](int u, int v){return deg[u] < deg[v];});
	int k = 0, sum = 0, last = n - 1;
	FOR(i, 0, n) {
		sum += deg[vertices[i]];
		if (sum + n - i - 1 <= 2 * (n - 1)) {
			k = i + 1;
			last = 2 * (n - 1) - (sum + n - i - 2);
		}
	}
	FOR(i, k, n - 1) {
		deg[vertices[i]] = 1;
	}
	if (k < n) {
		deg[vertices[n - 1]] = last;
	}
	set<pair<int, int>> s;
	FOR(i, 0, n) {
		s.emplace(deg[i], i);
	}
	cout << n - k << "\n" << n << " " << n - 1 << "\n";
	while (SZ(s) > 1) {
		auto [deg1, v1] = *s.begin();
		s.erase(s.begin());
		auto [deg2, v2] = *prev(s.end());
		s.erase(prev(s.end()));
		assert(deg1 == 1);
		cout << v1 << " " << v2 << "\n";
		s.emplace(deg2 - 1, v2);
	}
}