/*
         --┬--  |     |  --┬--                |       |
           |    |\    |    |                  |       |
           |    | \   |    |     ----->       |       |
           |    |  \  |    |                  |       |
           |    |   \ |    |                  |       |
         --┴--  |    \|    |                  └----   └----

*/

#define pragma

#ifdef pragma
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#endif // pragma

#include<bits/stdc++.h>

#define ll long long
#define all(x) begin(x),end(x)
#define pb push_back
#define x first
#define y second
#define int long long

using namespace std;

typedef vector<int> vi;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef long double ld;
typedef vector<vi> matrix;

const int INF = 1e9 + 7;
const int MAXN = 1e6 + 7;
const ld EPS = 1e-9;
const ld PI = atan2(0, -1);

void seriy() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // cout << fixed << setprecision(6);
    #if _android
        freopen("input", "r", stdin);
        freopen("output", "w", stdout);
    #endif
}

struct pt {
    int x, y;
};

istream& operator>>(istream& is, pt& p) {
      is >> p.x >> p.y;
      return is;
}

ostream& operator<<(ostream& os, pt& p) {
      os << p.x << " " << p.y;
      return os;
}

matrix g;
vector<pt> ans, tans;
vi used;

void dfs(int u, int dep) {
    used[u] = 1;
    for(auto v : g[u]) {
        if(!used[v] && dep < 2) {
            tans.pb({u + 1, v + 1});
            dfs(v, dep + 1);
        }
    }
}

signed main() {
    seriy();
    int n, m;
    cin >> n >> m;
    g.resize(n);
    used.resize(n);
    map<pii, bool> no;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        no[{u, v}] = 1;
        no[{v, u}] = 1;
    }
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            if(!no[{i, j}] && !no[{j, i}]) {
                g[i].pb(j);
                g[j].pb(i);
            }
        }
    }
    int mn = INF;
    for(int i = 0; i < n; i++) {
        used.assign(n, 0);
        tans.clear();
        queue<pii> q;
        q.push({i, 0});
        used[i] = 1;
        while(!q.empty()) {
            pii u = q.front();
            q.pop();
            for(auto v : g[u.x]) {
                if(!used[v] && u.y < 2) {
                    tans.pb({u.x + 1, v + 1});
                    used[v] = 1;
                    q.push({v, u.y + 1});
                }
            }
        }
        if(accumulate(all(used), 0) == n && tans.size() < mn) {
            mn = tans.size();
        }
    }
    for(int i = 0; i < n; i++) {
        used.assign(n, 0);
        tans.clear();
        queue<pii> q;
        q.push({i, 0});
        used[i] = 1;
        while(!q.empty()) {
            pii u = q.front();
            q.pop();
            for(auto v : g[u.x]) {
                if(!used[v] && u.y < 2) {
                    tans.pb({u.x + 1, v + 1});
                    used[v] = 1;
                    q.push({v, u.y + 1});
                }
            }
        }
        cout << accumulate(all(used), 0) << '\n';
        if(accumulate(all(used), 0) == n && tans.size() == mn) {
            cout << tans.size() << '\n';
            for(auto i : tans) {
                cout << i << '\n';
            }
            return 0;
        }
    }

    return 0;
}