#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NMAX 260
int n,lg,nrm;
int st[NMAX],dr[NMAX],viz[NMAX],l[NMAX];
int *G[NMAX];

void citire()
{
 FILE *fin=fopen("strazi.in","r");
 int m,i;
 fscanf(fin,"%d %d",&n,&m);
 for (i=1;i<=n;i++) { G[i]=(int*)realloc(G[i],sizeof(int)); G[i][0]=0;}
 while (m--)
  {int x,y;
   fscanf(fin,"%d %d",&x,&y);
   G[x][0]++;
   G[x]=(int*) realloc(G[x],(G[x][0]+1)*sizeof(int));
   G[x][G[x][0]]=y;
  }
 fclose(fin);
}

int cupleaza(int x)
{ int i;
 if (viz[x]) return 0;
 viz[x]=1;
 for (i=1;i<=G[x][0];i++)
  if (!dr[G[x][i]])
   {
    st[x]=G[x][i];
    dr[G[x][i]]=x;
    return 1;
   }
 for (i=1;i<=G[x][0];i++)
  if (cupleaza(dr[G[x][i]]))
    {
     st[x]=G[x][i];
     dr[G[x][i]]=x;
     return 1;
    }
 return 0;
}

void afisare()
{
 FILE *fout=fopen("strazi.out","w");
 fprintf(fout,"%d\n",nrm);
 int i;
 for (i=1;i<n;i++)
  if (viz[l[i+1]]==2) fprintf(fout,"%d %d\n",l[i],l[i+1]);
 for (i=1;i<=n;i++)
  fprintf(fout,"%d ",l[i]);
 fprintf(fout,"\n");
 fclose(fout);
}

int main()
{
 citire();
 memset(st,0,sizeof(st));
 memset(dr,0,sizeof(dr));
 int change=1,i;
 while (change)
  {
   memset(viz,0,sizeof(viz));
   change=0;
   for (i=1;i<=n;i++)
    if (!st[i])
       change|=cupleaza(i);
  }
 memset(viz,0,sizeof(viz));
 nrm=-1; lg=0;
 int x;
 for (i=1;i<=n&&lg<n;i++)
  if (!viz[i]&&st[i])
   {
    x=i; viz[i]=1; nrm++;
    while (x&&lg<n)
     {
      l[++lg]=x; viz[x]++;
      x=st[x];
     }
   }
 if (lg<n)
 for (i=1;i<=n;i++)
  if (!viz[i]) {viz[i]=2; l[++lg]=i;nrm++;}
 afisare();
 return 0;
}