#include <cstdio>
#include <vector>
#define dim 260

using namespace std;

int n, m, fol[dim], l[dim], r[dim];

vector<int> g[dim], a[dim];

int pairup(int x)
{
 vector<int>::iterator it;
 if (fol[x]) return 0;
 fol[x]=1;
 for (it=g[x].begin(); it!=g[x].end(); it++)
 if (!r[*it])
 {
  l[x]=*it;
  r[*it]=x;
  return 1;
 }
 for (it=g[x].begin(); it!=g[x].end(); it++)
  if (pairup(r[*it]))
  {
   l[x]=*it;
   r[*it]=x;
   return 1;
  }
 return 0;
}

int main()
{
 int i, x, y, count=1;
 freopen("strazi.in", "r", stdin);
 freopen("strazi.out", "w", stdout);
 scanf("%d %d\n", &n, &m);
 for (i=1; i<=m; i++)
 {
  scanf("%d %d\n", &x, &y);
  g[x].push_back(y);
 }
 while (count)
 {
  count=0;
  memset(fol, 0, sizeof(fol));
  for (i=1; i<=n; i++)
  if (!l[i]) count|=pairup(i);
 }
 count=-1;
 for (i=1; i<=n; i++)
 {
  if (r[i]) continue;
  count++;
  x=i;
  do
  {
   a[count].push_back(x);
   x=l[x];
  } while (x);
 }
 printf("%d\n", count);
 for (i=0; i<count; i++)
  printf("%d %d\n", a[i].back(), a[i+1].front());
 for (i=0; i<=count; i++)
  for (vector<int>::iterator it=a[i].begin(); it!=a[i].end(); it++)
   printf("%d ", *it);
 printf("\n");
 return 0;
}