#include <cstdio>
#include <vector>
#include <algorithm>
#define INF "strazi.in"
#define OUF "strazi.out"
#define NMAX 16
#define pb push_back
#define sz(arg) arg.size()
using namespace std;

char a[NMAX][NMAX]={0};
int main()
{
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	vector<short> sol,psol;
	short n,m,i,x,y,min,nr;
	fscanf(in,"%hd%hd",&n,&m);
	for(i=1;i<=m;++i)
	{
		fscanf(in,"%hd%hd",&x,&y);
		a[x][y]=1;
	}

	min=n+1;
	for(i=1;i<=n;++i) {sol.pb(i);psol.pb(i);}
	do
	{
		nr=0;
		for(i=1;i<n;++i)
			if(!a[psol[i-1]][psol[i]]) ++nr;
		if(nr<min){ for(i=0;i<n;++i) sol[i]=psol[i]; min=nr;}
	}while(next_permutation(psol.begin(),psol.end()));

	fprintf(out,"%hd\n",min);
	for(i=1;i<n;++i)
		if(!a[sol[i-1]][sol[i]]) fprintf(out,"%hd %hd\n",sol[i-1],sol[i]);
	for(i=0;i<n;++i) fprintf(out,"%hd ",sol[i]);

	fclose(in);fclose(out);
	return 0;
}