#include <bits/stdc++.h>

using namespace std;
class Matcher {
    int n, m;
    vector <int> l, r;
    vector <bool> upd;
    vector <vector <int>> g;
    inline bool pairup(int u) {
        if(upd[u]) return false;
        upd[u] = true;
        for(int v : g[u]) if(!l[v])
            return l[r[u] = v] = u, true;
        for(int v : g[u]) if(pairup(l[v]))
            return l[r[u] = v] = u, true;
        return false;
    }
public:
    Matcher(int n, int m) : n(n), m(m), r(n + 1, 0), l(m + 1, 0), upd(n + 1, false), g(n + 1) {}
    void add_edge(int u, int v) { g[u].push_back(v); }
    vector <pair <int, int>> match() {
        for(bool ok = true; ok; fill(upd.begin(), upd.end(), false)) {
            ok = false;
            for(int i = 1; i <= n; i++) if(!r[i])
                ok |= pairup(i);
        }
        vector <pair <int, int>> sol;
        for(int i = 1; i <= n; i++) if(r[i])
            sol.emplace_back(i, r[i]);
        return sol;
    }
};
const int N = 1 << 8;
vector <int> path;
vector <pair <int, int>> sol;
bool vis[N + 5], top[N + 5];
int l[N + 5];

int main()
{
    ifstream cin("strazi.in");
    ofstream cout("strazi.out");
    int n, m;
    cin >> n >> m;
    Matcher M(n, n);
    for (int i = 1, u, v; i <= m; i++)
        cin >> u >> v,
        M.add_edge(u, v);
    auto v = M.match();
    fill(top + 1, top + n + 1, true);
    for(auto x : v)
      //cerr << x.first << " " << x.second << "\n",
      l[x.first] = x.second,
      top[x.second] = false;
    cout << n - (int)v.size() - 1 << "\n";
    int last = 0;
    vector <int> p;
    for(int i = 1; i <= n; i++) if(top[i])
      p.push_back(i);
    for(int i : p) if(!vis[i]) {
      //cerr << i << ":";
      if(last) sol.emplace_back(last, i);
      for(; l[i]; i = l[i])
        path.push_back(i),
        vis[i] = true;
      path.push_back(i);
      last = i;
    }
    for(auto x : sol)
      cout << x.first << " " << x.second << "\n";
    for(int x : path)
      cout << x << " ";
    return 0;
}