#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int N = 1e4 + 5, mod = 1e9 + 7, A = 26;
int co[N];


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        co[a]++;
        co[b]++;
    }
    deque<pair<int, int>> dq;
    for (int i = 0; i < n; i++)
        dq.push_back({co[i], i});
    sort(dq.begin(), dq.end());
    //v.back().first++;
    vector<pair<int, int>> ans;
    int cobad = 0;
    deque<int> q;
    while (dq.size()) {
        auto it = dq.front();
        dq.pop_front();
        it.first--;
        while (q.size() < it.first && dq.size()) {
            cobad++;
            q.push_back(dq.back().second);
            dq.pop_back();
        }
        if (dq.empty()) {
            if (q.size() != it.first + 1) {
                cobad++;
            }
            while (q.size()) {
                ans.push_back({it.second, q.front()});
                q.pop_front();
            }
            break;
        }

        if (q.size() >= it.first) {
            for (int i = 0; i < it.first; i++) {
                ans.push_back({it.second, q.front()});
                q.pop_front();
            }
            q.push_back(it.second);
        } else {
            cobad++;
            if (q.size() == 0) {
                cobad++;
                for (int i = 0; i < n; i++) {
                    if (i != it.second) {
                        ans.push_back({i, it.second});
                        break;
                    }
                }
            }
            while (q.size()) {
                ans.push_back({it.second, q.front()});
                q.pop_front();
            }
        }
    }
    cout << cobad << "\n";
    cout << n << " " << n - 1 << "\n";
    for (auto it: ans)
        cout << it.first << " " << it.second << "\n";


    return 0;
}