#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<pair<int,int>> deg(n, {0,0});

    for(int i = 0; i < n; i++) deg[i].second = i;

    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        deg[u].first++;
        deg[v].first++;
    }

    sort(deg.begin(), deg.end());

    queue<int> qw;

    vector<pair<int,int>> ans(0);
    int resp = 0;

    int p2 = n-1; 

    for(int i = 0; i < p2; i++){
        int x = deg[i].first, ind = deg[i].second;
        x--;

        // cout << x << ' ' << ind << endl;

        while(x > qw.size() && i < p2){
            int h = deg[p2--].second;

            qw.push(h);
        }

        if(i >= p2) break;

        for(int j = 0; j < x; j++){
            int h = qw.front(); qw.pop();
            ans.push_back({ind, h});
        }
        qw.push(ind);
        resp++;
    }

    int x = deg[p2].first, ind = deg[p2].second;

    if(x == qw.size()){
        resp++;
    }

    while(!qw.empty()){
        int h = qw.front(); qw.pop();
        ans.push_back({ind, h});
    }

    cout << n-resp << endl;
    cout << n << ' ' << n-1 << endl;

    for(auto[a,b]: ans) cout << a << ' ' << b << endl;

    return 0;
}