#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())

const int N = 10005;

int dp[N][N], frm[N][N], deg[N], fin[N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        ++u, ++v;
        ++deg[u], ++deg[v];
    }
    for (int i = 1; i <= n; ++i) {
        pii mx = pii(-n, 0), smx = pii(-n, 0);
        for (int j = 0; j < n; ++j) {
            dp[i][j] = -n;
            if (dp[i - 1][j] > mx.X)
                smx = mx, mx = pii(dp[i - 1][j], j);
            else if (dp[i - 1][j] > smx.X)
                smx = pii(dp[i - 1][j], j);

            auto check = [&](int k, int v) {
                if (v > dp[i][j]) {
                    dp[i][j] = v;
                    frm[i][j] = k;
                }
            };

            if (deg[i] - 1 <= j) {
                int v = dp[i - 1][j - (deg[i] - 1)];
                check(j - (deg[i] - 1), v + 1);
                if (mx.X == v) check(smx.Y, smx.X);
                else check(mx.Y, mx.X);
            }
            else
                check(mx.Y, mx.X);
        }
    }

    set<pii> st;
    int ans = dp[n][n - 2];
    int cur = n - 2, nw = n;
    while (nw > 0) {
        int nxt = frm[nw][cur];
        fin[nw] = cur - nxt + 1;
        st.insert(pii(fin[nw], nw));
        cur = nxt, --nw;
    }

    vector<pii> edge;
    while (SZ(st) > 1) {
        int a = st.begin()->Y;
        st.erase(st.begin());
        int b = st.rbegin()->Y;
        st.erase(--st.end());
        edge.pb(pii(a, b));
        --fin[a], --fin[b];
        if (fin[a] > 0) st.insert(pii(fin[a], a));
        if (fin[b] > 0) st.insert(pii(fin[b], b));
    }

    cout << n - ans << "\n";
    cout << n << " " << n - 1 << "\n";
    for (auto [u, v] : edge)
        cout << u - 1 << " " << v - 1 << "\n";
}