#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define ld long double
#define int long long
#define ll __int128

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 1e5 + 10;
int was[N], mt[N], used[N];
vector<pair<int,int>> show;
vector<int> now, g[N];
int cnt = 1;

bool dfs(int v, int now){
    if (used[v] == now) return 0;
    used[v] = now;
    for (auto to : g[v]){
        if (mt[to] == -1) {
            mt[to] = v;
            if (mt[v] != -1) mt[mt[v]] = -1;
            mt[v] = to;
            return 1;
        }
    }
    for (auto to : g[v]){
        used[to] = now;
        if (dfs(mt[to], now)){
            if (mt[to] != -1) mt[mt[to]] = -1;
            mt[to] = v;
            if (mt[v] != -1) mt[mt[v]] = -1;
            mt[v] = to;
            return 1;
        }
    }
    return 0;
}


void solve(vector<int> a){
    for (auto i : a) mt[i] = -1;
    for (auto i : a){
        shuffle(g[i].begin(), g[i].end(), rnd);
    }
    for (int i = 0; i < a.size(); i++){
        for (auto j : a){
            if (mt[j] == -1){
                dfs(j, cnt++);
            }
        }
    }
    vector<pair<int,int>> now;
    for (auto i : a){
        if (mt[i] > i){
            now.pb({i, mt[i]});
        }
    }
    if (now.size() > show.size()) show = now;
}

void walk(int v){
    was[v] = 1;
    now.pb(v);
    for (auto to : g[v]){
        if (!was[to]){
            walk(to);
        }
    }
}

int32_t main()
{
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    vector<pair<int,int>> ans;
    for (int i = 0; i < n; i++){
        if (!was[i]){
            now.clear();
            walk(i);
            for (int i = 0; i < n; i++) solve(now);
            for (auto to : show){
                ans.pb(to);
            }
            show.clear();
        }
    }
    cout << ans.size() << endl;
    for (auto to : ans){
        cout << to.first << ' ' << to.second << endl;
    }
    return 0;
}