#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1 << 8;

vector <int> g[MAXN];
int seen[MAXN], l[MAXN], r[MAXN], from[MAXN];

int match(int node) {
  if (seen[node])
    return 0;
  seen[node] = 1;
  for (auto it : g[node])
    if (r[it] == 0) {
      l[node] = it;
      r[it] = node;
      return 1;
    }
  for (auto it : g[node])
    if (match(r[it])) {
      l[node] = it;
      r[it] = node;
      return 1;
    }
  return 0;
}

void dfs(int node, vector <int> &v) {
  if (node == 0)
    return;
  v.push_back(node);
  dfs(from[node], v);
}

int main()
{
    int n, m;
    ifstream fin("strazi.in");
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
      int x, y;
      fin >> x >> y;
      g[x].push_back(y);
    }
    fin.close();
    int augm;
    do {
      augm = 0;
      memset(seen, 0, sizeof seen);
      for (int i = 1; i <= n; ++i)
        if (l[i] == 0)
          augm += match(i);
    } while (augm);
    for (int i = 1; i <= n; ++i) {
      augm += (l[i] > 0);
      from[i] = r[i];
    }
    vector <vector <int>> chains;
    for (int i = 1; i <= n; ++i)
      if (l[i] == 0) {
        vector <int> aux;
        dfs(i, aux);
        reverse(aux.begin(), aux.end());
        chains.push_back(aux);
      }
    ofstream fout("strazi.out");
    fout << n - augm - 1 << '\n';
    for (int i = 1; i < (int) chains.size(); ++i)
      fout << chains[i - 1].back() << " " << chains[i].front() << '\n';
    for (auto ch : chains)
      for (auto it : ch)
        fout << it << " ";
    fout.close();
    return 0;
}