#include <cstdio>

#define dim 256

int N;
int M;

int Min = 0x3f3f3f3f;

int A[dim][dim];
int S[dim];
int U[dim];

int Sol[dim];

void back(int k)
{
	if(k == N + 1)
	{
		int i, c = 0;

		for(i=2; i<=N; ++i)
			if(!A[S[i-1]][S[i]])
				++ c;
		
		if(c < Min)
		{
			Min = c;
			
			for(i=1; i<=N; ++i)
				Sol[i] = S[i];
		}
	}
	else
	{
		int i;
		
		for(i=1; i<=N; ++i)
			if(!U[i])
			{
				S[k] = i;
				U[i] = 1;
				
				back(k + 1);
				
				U[i] = 0;
			}
	}
}

int main()
{
	freopen("strazi.in", "rt", stdin);
	freopen("strazi.out", "wt", stdout);
	
	int i, a, b;
	
	for(scanf("%d %d", &N, &M), i=1; i<=M; ++i)
	{
		scanf("%d %d", &a, &b);
		
		A[a][b] = 1;
	}

	back(1);

	printf("%d\n", Min);
	
	for(i=2; i<=N; ++i)
		if(!A[Sol[i-1]][Sol[i]])
			printf("%d %d\n", Sol[i-1], Sol[i]);
	
	for(i=1; i<=N; ++i)
		printf("%d ", Sol[i]);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}