#include<stdio.h>
#include<stdlib.h>
int n,m,a[256][256]={0},MIN=0,sol[256][2],ut[256],komp[256]={0},ek,lat[256]={0},maxk=0,k,hanyas;
int bk[256][2]={0},maxm;
void kiir();
void beolvas()
{
	FILE *f=fopen("strazi.in","r");
	fscanf(f,"%d%d",&n,&m);
	int i,x,y;
	for(i=0;i<m;i++)
	{
		fscanf(f,"%d%d",&x,&y);
		a[x][y]=1;
	}
	for(i=1;i<=n;i++)
		komp[i]=i;
	fclose(f);
}
void bejar(int x)
{
	lat[x]=1;
	komp[x]=ek;
	k++;
	for(int i=1;i<=n;i++)
		if(a[x][i]&&!lat[i])
		{
			bejar(i);
			i=n;
		}
}
void nullaz()
{
	for(int i=1;i<=n;i++) lat[i]=0;
}
int egyforma()
{
	int i,x=komp[1];
	for(i=1;i<=n;i++)
		if(komp[i]!=x) return 0;
	return 1;
}
void be_ki_fokszamok()
{
	int i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(a[i][j]) 
			{
				bk[i][1]++;
				bk[j][0]++;
			}
}
void bejarul(int x,int *m)
{
	int i;
	lat[x]=1;
	for(i=1;i<=n;i++)
		if(a[x][i]&&!lat[i])
		{
			(*m)++;
			if((*m)>maxm) maxm=*m;
			bejarul(i,m);
		}
	(*m)--;
	lat[x]=0;
}
void utepit(int x,int melyseg)
{
	if(melyseg==maxm)
	{
		ut[maxm]=x;
		kiir();
		exit(0);
	}
	int i;
	lat[x]=1;
	for(i=1;i<=n;i++)
		if(a[x][i]&&!lat[i])
		{
			melyseg++;
			ut[melyseg]=i;
			utepit(i,melyseg);

		}
	melyseg--;
	ut[melyseg]=0;
	lat[x]=0;
}
void probal_utak()
{
	int um;
	if(n==1)
	{
		ut[1]=1;
		return;
	}
	int i,j;
	i=0;
	maxm=1;
	while(maxm!=n)
	{
		um=1;
		i++;
		nullaz();
		ut[1]=i;
		bejarul(i,&um);
	}
	nullaz();
	utepit(i,1);
}
void megold()
{
	int i;
	be_ki_fokszamok();
	for(i=1;i<=n;i++)
		if(komp[i]==i) 
		{
			k=0;
			nullaz();
			ek=i;
			bejar(i);
			if(k>maxk) {maxk=k;hanyas=i;}
		}
	int maxk2,mk,j,hanyas2=0;
	while(!egyforma())
	{
		maxk2=0;
		mk=1;
		for(i=1;i<=n;i++)
			if(komp[i]!=hanyas)
			{
				mk=1;
				if(komp[i+1]!=komp[i]&&!hanyas2)
					hanyas2=i;
				else
					for(j=i+1;komp[j]==komp[i];j++,mk++);
				if(mk>maxk2)
				{
					maxk2=mk;
					hanyas2=komp[i];
				}
			}
		int kitol=0;
		for(i=1;i<=n&&!kitol;i++)
			if(komp[i]==hanyas&&!kitol)
				if(!bk[i][1]) kitol=i;
		for(i=1;i<=n;i++)
			if(komp[i]==hanyas2)
			{
				if((bk[i][0]==0&&bk[i][1]>=1)||(maxk2==1))
				{
					MIN++;
					sol[MIN][0]=kitol;
					sol[MIN][1]=i;
					a[kitol][i]=1;
					bk[kitol][1]++;
					bk[i][0]++;
					for(j=1;j<=n;j++)
						if(komp[j]==hanyas2)
							komp[j]=hanyas;
				}
			}
	}
	probal_utak();
}
void kiir()
{
	FILE *f=fopen("strazi.out","w");
	fprintf(f,"%d\n",MIN);
	int i;
	for(i=1;i<=MIN;i++)
		fprintf(f,"%d %d\n",sol[i][0],sol[i][1]);
	for(i=1;i<=n;i++)
		if(i==n) fprintf(f,"%d",ut[i]);
		else fprintf(f,"%d ",ut[i]);
	fclose(f);
}
void main()
{
	beolvas();
	megold();
	kiir();
}