#include <stdio.h>
#include <string.h>

#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define nmax 256

int n,l[nmax],r[nmax],sol,m;
char G[nmax][nmax],viz[nmax];

int pairup(int i)
{
	if(viz[i]) return 0;
	viz[i]=1;
	int j;
	FOR(j,0,n)
		if(G[i][j] && l[j]==-1)
		{
			r[i]=j, l[j]=i;
			return 1;
		}
	FOR(j,0,n)
		if(G[i][j] && pairup(l[j]))
		{
			r[i]=j, l[j]=i;
			return 1;
		}
	return 0;
}

int main()
{
	freopen("strazi.in","r",stdin);
	freopen("strazi.out","w",stdout);
	int i,j,ii,a;
	scanf("%d %d",&n,&m);
	memset(G,0,sizeof(G));
	FOR(ii,0,m)
	{
		scanf("%d %d",&i,&j);
		i--,j--;
		G[i][j]=1;
	}
	memset(l,-1,sizeof(l));
	memset(r,-1,sizeof(r));
	memset(viz,0,sizeof(viz));
	FOR(i,0,n)
		if(pairup(i))
			sol++,memset(viz,0,sizeof(viz));
	printf("%d\n",n-sol-1);
	FOR(i,0,n)
		if(l[i]==-1)
			break;
	a=i;
	FOR(j,0,n)
	{
		if(r[i]==-1)
			FOR(ii,0,n)
				if(l[ii]==-1&& ii!=a)
				{
					printf("%d %d\n",i+1,ii+1);
					l[ii]=i, r[i]=ii;
					break;
				}
		i=r[i];
		viz[i]=1;
	}
	ii=a;
	FOR(i,0,n)
		printf("%d ",ii+1),ii=r[ii];
	printf("\n");
	return 0;
}