#include<stdio.h>
long int n,m,i,A,B,a[260][260],min,nv,viz[260],p[260],
sx[260],sy[260],ex[260],ey[260],ad,ps[260];
void back();
int main()
{
	FILE *f,*g;f=fopen("strazi.in","r");g=fopen("strazi.out","w");
	fscanf(f,"%ld%ld",&n,&m);
	for(i=1;i<=m;i++){fscanf(f,"%ld%ld",&A,&B);a[A][B]=1;}
	min=n+5;
	for(i=1;i<=n;i++)
	{p[1]=i;nv=1;viz[i]=1;
	 back();
	 viz[i]=0;
	}
	fprintf(g,"%ld\n",min);
	for(i=1;i<=min;i++)
	fprintf(g,"%ld %ld\n",sx[i],sy[i]);
	for(i=1;i<=n;i++)
        fprintf(g,"%ld ",ps[i]);
	fcloseall();
	return 0;
}
void back()
{       long int ii;
	if(nv==n)
	{ min=ad;
	  for(ii=1;ii<=min;ii++)
	  { sx[ii]=ex[ii];sy[ii]=ey[ii];}
	  for(ii=1;ii<=n;ii++)ps[ii]=p[ii];
	}
	if(ad==min-1)return;
	for(ii=1;ii<=n;ii++)
	 if(!viz[ii])
	 { viz[ii]=1;nv++;p[nv]=ii;
	   if(!a[p[nv-1]][p[nv]])
	   { ad++;ex[ad]=p[nv-1];ey[ad]=p[nv];back();ad--;}
	   else back();
	   viz[ii]=0;nv--;
	 }
}