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

#define maxm 260
#define maxn 18
#define maxx 1<<18

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

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];
}

void DFS(int nod)
{
	u[nod] = 1;
	s[++l] = nod;
	int i;
	for (i=0;i<n;i++)
		if (a[nod][i] && !u[i]) 
		{
			DFS(i);
			break;
		}
}

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;
		g[y]++;
	}

	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");
	}
	else {
			 for (i=0;i<n;i++)	
				 if (u[i] == 0)
				 {
					 DFS(i);
					 sol++;
				 }
				 

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

			 for (i=1;i<l;i++)
			 	if (!a[s[i]][s[i+1]]) printf("%d %d\n",s[i]+1,s[i+1]+1);
		  	 for (i=1;i<=l;i++) printf("%d ",s[i]+1);
		  	 printf("\n");
		 		
	     }

	return 0;
}