#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

#define INF 0x0fffffff

char graf[256][256];

int main ()
{
	freopen("strazi.in", "r", stdin);
	freopen("strazi.out", "w+", stdout);
	unsigned int bestperm[256], bestadded=INF;
	
	clock_t startTime = clock();
	srand(time(NULL));
	
	unsigned int N,M,i;
	scanf("%u %u", &N, &M);
	for (i=0; i<M; ++i) {
		unsigned int src, dest;
		scanf("%u %u\n", &src, &dest);
		graf[src][dest] = 1;
	}
#	ifdef MYD
	unsigned int tried=0;
#	endif
	while (bestadded > 1 && (double)(clock() - startTime)/CLOCKS_PER_SEC < .193) {
#		ifdef MYD
		++tried;
#		endif
		unsigned int perm[256];
		for (i=0; i<N; ++i) perm[i]=i+1;
		for (i=0; i<N-1; ++i) swap(perm[i], perm[i+rand()%(N-i)]);
		unsigned int added=0;
		for (i=0; i<N-1; ++i) if (!graf[perm[i]][perm[i+1]]) ++added;
		if (added < bestadded) { bestadded = added; memcpy(bestperm, perm, sizeof(perm)); }
	}
#	ifdef MYD
	fprintf(stderr, "Tried %u random permutations.\n", tried);
#	endif
	printf("%u\n", bestadded);
	for (i=0; i<N-1; ++i)
		if (!graf[bestperm[i]][bestperm[i+1]]) printf("%u %u\n", bestperm[i], bestperm[i+1]);
	for (i=0; i<N; ++i)
		printf("%u ", bestperm[i]);
	printf("\n");
	return 0;
}