#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <set>
#include <map>
#include <array>

using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()

const int N = 1e5 + 3;

int d[N], n, m;
int new_d[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int u, v;
        cin >> u >> v;
        ++d[u];
        ++d[v];
    }

    vector<pair<int, int>> v;
    for(int i = 0; i < n; ++i){
        v.push_back({d[i], i});
    }

    sort(all(v));

    int sum = 0, ans = 0;
    for(int i = 0; i < n; ++i){
        if(sum + v[i].first + n - i - 1 > 2 * (n - 1)){
            ans = n - i;
            for(; i < n - 1; ++i){
                new_d[v[i].second] = 1;
                ++sum;
            }
            new_d[v.back().second] = 2 * (n - 1) - sum;
            break; 
        }

        new_d[v[i].second] = v[i].first;
        sum += v[i].first;
    }

    set<pair<int, int>> s;
    for(int i = 0; i < n; ++i){
        s.insert({new_d[i], i});
    }

    cout << ans << "\n";
    cout << n << " " << n - 1 << endl;
    for(int i = 0; i < n - 1; ++i){
        // cout << s.size() << " s size " << i << endl;
        auto [du, u] = *s.begin();
        s.erase(s.begin());

        auto [dv, v] = *s.rbegin();
        s.erase({dv, v});

        --dv;
        cout << v << " " << u << "\n";
        if(dv){
            s.insert({dv, v});
        }
    }
}