#include <cstdio>

#define fin  "strazi.in"
#define fout "strazi.out"

const int Nmax = 256;
const int MAX  = 1000000;

int N,M,g[Nmax][Nmax];
int bst;
int sol[Nmax],x[Nmax],used[Nmax];

void readdata()
{
	int i,x,y;

	freopen(fin,"r",stdin);	
	scanf("%d%d",&N,&M);

	for (i=1;i<=M;++i)
		scanf("%d%d",&x,&y),g[x][y]=1;
	for (i=1;i<=N;++i)
		g[0][i]=1;

	bst=MAX;
}

void go(int lev,int cost)
{
	int i;

	if ( cost >= bst )
		return ;

	if ( lev == N + 1 )
	{
		if ( cost < bst )
		{
			for (i=1;i<=N;++i)
				sol[i]=x[i];
			bst = cost;
		}
	}
	else
		for (i=1;i<=N;++i)
			if (!used[i])
			{
				used[i]=1;
				x[lev]=i;
				go(lev+1,cost + ( g[ x[lev-1] ][ i ] ^ 1 ) );
				used[i]=0;
			}
}

void printdata()
{
	int i;

	freopen(fout,"w",stdout);

	printf("%d\n",bst);

	for (i=2;i<=N;++i)
		if ( g[sol[i-1]][sol[i]] == 0 )
			printf("%d %d\n",sol[i-1],sol[i]);

	for (i=1;i<=N;++i)
		printf("%d ",sol[i]);
	printf("\n");
}

int main()
{
	readdata();
	go(1,0);
	printdata();
	return 0;
}