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

#define ll long long


const int N=1e6+5;

signed main() {
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);

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

    vector<int> deg(n,0),ndeg(n,1);
    vector<int> a,b;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        deg[u]++;
        deg[v]++;
    }

    for(int i=0;i<n;i++){
        a.push_back(i);
        b.push_back(i);
    }

    sort(a.begin(),a.end(),[&](int x, int y) {
        return deg[x]<deg[y];
    });

    int rem=n-2;
    int curr=0;
    int ans=0;
    while(curr<n){
        int x=deg[a[curr]];
        

        x--;

        if(x>rem){
            ndeg[a[curr]]+=rem;
            rem=0;
            break;
        }
        else{
            ndeg[a[curr]]+=x;
            rem-=x;
            ans++;
        }
        curr++;
    }
    // cout<<ans<<"\n";
    // cout<<rem<<"\n";
    // cout<<"done\n";
    // for(auto it:ndeg) cout<<it<<" ";
    // cout<<"\n";
    sort(b.begin(),b.end(),[&](int x, int y) {
        return ndeg[x]>ndeg[y];
    });
    curr=1;
    vector<pair<int,int>> ed;

    for(int i=0;i<n;i++){
        int val=ndeg[b[i]];
       // cout<<b[i]<<" "<<val<<"\n";
        while(val){
            ed.push_back({b[i],b[curr]});
            ndeg[b[curr]]--;
            val--;
            curr++;
            //cout<<curr<<"\n";
        }
    }

    assert(ed.size()==n-1);

    cout<<n-ans<<"\n";
    cout<<n<<" "<<n-1<<"\n";
    for(auto it:ed) cout<<it.first<<" "<<it.second<<"\n";




}