#include "bits/stdc++.h"

using namespace std;
using lint = int64_t;

int main(void) {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m; cin>>n>>m;
    vector<int> degree(n);
    for(int e =0; e<m; e++){
        int u,v;
        cin>>u>>v;
        degree[u]++;
        degree[v]++;
    }
    //sum = 2*(n-1) - n = n-2
    const int L = n-2;
    vector<vector<int>> link(n+1, vector<int>(L+1, -1));
    vector<vector<int>> dp(n+1, vector<int>(L+1, -2*n));
    dp[0][0] = 0;
    int maxi = 0;
    for(int i =0; i <n; i++){
        dp[i+1] = dp[i];
        link[i+1] = link[i];
        const int d = degree[i] - 1;
        for(int tam = L; tam >= d; tam--){
            if(dp[i+1][tam] < dp[i][tam-d] + 1){
                dp[i+1][tam] = dp[i][tam-d] + 1;
                link[i+1][tam] = i;
            }
            maxi = max(maxi, dp[i+1][tam]);
        }
    }

    vector<int> new_degree(n, 1);
    vector<bool> selected(n);
    for(int k = 0; k <=n; k++) for(int i = 0; i <=L; i++) if(dp[k][i] == maxi){
        int cur = i;
        int l = link[k][i];
        int answer = dp[k][i];
        while(l != -1){
            selected[l] = true;
            new_degree[l] = degree[l];
            cur = cur - (degree[l] - 1);
            l = link[l][cur];
        }
        for(int j =0; j < n; j++){
            if(!selected[j]){
                selected[j] = true;
                new_degree[j] += n-2-i;
                break;
            }
        }

        vector<int> ids(n);
        iota(ids.begin(), ids.end(), 0);
        sort(ids.begin(), ids.end(), [&](int a, int b){
            return new_degree[a] > new_degree[b];
        });
        cout<<n-answer<<"\n";
        cout<<n<<" "<<n-1<<"\n";
        for(int l = 0, r = 1; l < n; l++){
            const int a = ids[l];
            while(new_degree[a]){
                new_degree[a]--;
                cout<<a<<" "<<ids[r]<<"\n"; 
                new_degree[ids[r]]--;
                r++;
            }
        }

        exit(0);
    }


    
    return 0;
}