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

#define maxn 18
#define maxx 1<<18

int n,m,sol;
int a[maxn][maxn];
char c[maxn][maxx],d[maxn][maxx];
int s[maxn],sx[maxn],sy[maxn];
int l,k;

int solve(int x,int y)
{
	if (c[x][y] == -1)
	{
		c[x][y] = n+1;

		int i;
		for (i=0;i<n;i++)
			if (y&(1<<i) && i!=x) 
			{
				int aux = solve(i,y^(1<<x)) + (a[i][x] == 0);
				
				if (aux < c[x][y])
				{
					c[x][y] = aux;
					d[x][y] = i;
				}
			}
	}

	return c[x][y];
}

int main()
{
	freopen("strazi.in","r",stdin);
	freopen("strazi.out","w",stdout);

	scanf("%d %d ",&n,&m);

	int i,x,y;

	for (i=1;i<=m;i++)
	{
		scanf("%d %d ",&x,&y);
		x--, y--;
		a[x][y] =  1;
	}

	if (n<=18) 
	{
		memset(c,-1,sizeof(c));	 

		for (i=0;i<n;i++) 
		{
			c[i][1<<i] = 0;
			d[i][1<<i] = -1;
		}

		sol = n + 1;

		for (i=0;i<n;i++) 
		{
			int aux = solve(i,(1<<n)-1);
			if (aux < sol)
			{
				sol = aux;
				x = i;
			}
		}

		y = (1<<n) - 1;

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

		while (x!=-1)
		{
			s[++l] = x;
			int aux = x;
			x=d[x][y];
			y ^= 1<<aux;
			if (x!=-1 && a[x][aux] == 0) 
			{
				k++;
				sx[k] = x;
				sy[k] = aux;
			}
		}

		for (i=1;i<=k;i++) printf("%d %d\n",sx[i]+1,sy[i]+1);
		for (i=l;i>0;i--) printf("%d ",s[i]+1);
		printf("\n");
	}

	return 0;
}