//nr minim de arce ce trebuie adaugat pt a forma un drum hamiltonian
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NMAX 260
int c[2*NMAX][2*NMAX],f[2*NMAX][2*NMAX];
int viz[2*NMAX],s,d,n,m,l[NMAX],nrm;

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

int bfs()
{ int Q[2*NMAX],p,u,x,i;
 p=u=0; Q[0]=s; viz[s]=1;
 while (p<=u&&viz[d]==-1)
  {
   x=Q[p++];
   if (x==s)
      {for (i=1;i<=n;i++)
	if (viz[i]==-1&&!f[s][i])
	   {
	    Q[++u]=i; viz[i]=s;
	   }
      }
     else
     if (x<=n)
      {
       for (i=n+1;i<=2*n;i++)
	if (viz[i]==-1)
	  if (f[x][i]<c[x][i]) {viz[i]=x; Q[++u]=i;}
	     else
	      if (f[x][i]){viz[i]=-x; Q[++u]=i;}
      }
      else //x=n+1....2*n
      {
       if (!f[x][d])viz[d]=x;
      }
  }
 return (viz[d]!=-1);
}

void flux()
{
 memset(f,0,sizeof(f));
 s=0; d=2*n+1;
 int i,lg;
 for (i=1;i<=n;i++) {c[s][i]=1; c[i+n][d]=1;}
 do
  {
   for (i=1;i<=2*n+1;i++)viz[i]=-1;
   if (!bfs()) return;
   lg=0; l[lg]=d;
   while (l[lg]!=s)
    {
     lg++;
     l[lg]=abs(viz[l[lg-1]]);
    }
   for (i=lg;i;i--)
    if (viz[l[i-1]]>=0) f[l[i]][l[i-1]]++;
       else f[l[i]][l[i-1]]--;
  }
 while (1);
}

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");
}

int main()
{
 citire();
 flux();
 memset(viz,0,sizeof(viz));
 int k,ok,i,x,y;
 nrm=-1; k=0;
 for (i=1;i<=n;i++)
  if (!viz[i]&&f[0][i])
     {
      nrm++;
      x=i; viz[x]=1;
      do
       {
	viz[x]++; l[++k]=x; ok=0;
	for (y=1;y<=n&&!ok;y++)
	 if (f[x][y+n]&&!viz[y])
	    { ok=1;
	      x=y;
	    }
       }
      while (ok);
     }
 for (i=1;i<=n;i++)
  if (!viz[i])
    {
     viz[i]=2; nrm++;
     l[++k]=i;
    }
 afisare();
 return 0;
}