#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=1e4+5;
const int M=1e5+5;
int n,m,d[N];
vector<pair<int,int> >a,b;
priority_queue<pair<int,int> >hp;
int main(){
	cin>>n>>m;
	rep(i,1,m){
		int u,v;
		cin>>u>>v;
		u++,v++;
		d[u]++,d[v]++;
	}
	rep(i,1,n) a.push_back({d[i],i});
	sort(a.begin(),a.end());
	int stp;
	rep(i,0,a.size()-1){
		if(a[i].first > 1){
			stp = i;
			break;
		}
	}

	int ans = 0;
	hp.push({-a[stp].first,a[stp].second});
	rep(i,stp+1,a.size()-1){
		auto cur = hp.top();
		hp.pop();
		hp.push({-a[i].first+1,a[i].second});
		b.push_back({a[i].second, cur.second});
		if(cur.first!=-1){
			hp.push({cur.first+1, cur.second});
		}else{
			ans++;
		}
	}
	rep(i,0,stp-1){
		auto cur = hp.top();
		hp.pop();
		ans++;
		b.push_back({a[i].second, cur.second});
		if(cur.first!=-1){
			hp.push({cur.first+1, cur.second});
		}else{
			ans++;
		}
	}
	cout<<n-ans<<'\n'<<n<<' '<<n-1<<'\n';
	for(auto w:b) cout<<w.first-1<<" "<<w.second-1<<'\n';
	return 0;
}
/*
7 11
0 1
0 2
0 5
0 6
1 3
2 4
1 2
1 2
1 5
2 6
5 6
*/