#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

ifstream in("strazi.in");
ofstream out("strazi.out");

const int N = 255;

int n, m;
int l[N + 5], r[2 * N + 5];
bitset<N + 5> vis;
vector<int> adj[N + 5], add;
vector<pair<int, int>> paths;

int encode(int x) {
    return (x > n ? x - n : x + n);
}

bool match(int x) {
    if (vis[x])
        return false;
    vis[x] = true;
    for (auto it: adj[x]) {
        if (r[it] == 0) {
            l[x] = it;
            r[it] = x;
            return true;
        }
    }
    for (auto it: adj[x]) {
        if (match(r[it])) {
            l[x] = it;
            r[it] = x;
            return true;
        }
    }
    return false;
}

int main() {
    in >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        in >> x >> y;
        adj[x].push_back(encode(y));
    }
    bool ok = true;
    while (ok) {
        ok = false;
        vis.reset();
        for (int i = 1; i <= n; i++)
            if (l[i] == 0)
                ok |= match(i);
    }
    for (int i = 1; i <= n; i++) {
        if (r[encode(i)] == 0) {
            pair<int, int> p;
            p.first = i;
            if(l[i] == 0)
                p.second = i;
            else {
                int x = encode(l[i]);
                while(l[x] != 0)
                    x = encode(l[x]);
                p.second = x;
            }
            paths.push_back(p);
        }
    }
    out << paths.size() - 1 << '\n';
    for (int i = 0; i < paths.size() - 1; i++) {
        l[paths[i].second] = encode(paths[i + 1].first);
        out << paths[i].second << ' ' << paths[i + 1].first << '\n';
    }
    int x = paths[0].first;
    while(l[x] != 0) {
        out << x << ' ';
        x = encode(l[x]);
    }
    out << x << '\n';
    return 0;
}