#include <cstdio>
#include <memory.h>
using namespace std;

const char iname[] = "strazi.in";
const char oname[] = "strazi.out";

#define MAXN  255

bool C[MAXN][MAXN];  int n;

int X[MAXN];

bool used[MAXN];

int ret = MAXN, R[MAXN];

void f(const int k)
{
	if (k == n + 1) {
		int cnt = 0;
		for (int i = 1; i < n; ++ i) if (!C[X[i]][X[i + 1]])
			cnt ++;
		if (ret > cnt)
			ret = cnt, memcpy(R, X, sizeof(X));
		return ;
	}
	for (X[k] = 1; X[k] <= n; ++ X[k]) if (!used[X[k]])
		used[X[k]] = 1, f(k + 1), used[X[k]] = 0;
}

int main(void)
{
	freopen(iname, "r", stdin);
	freopen(oname, "w", stdout);
	
	int cnt;
	int x, y;

	scanf("%d %d\n", &n, &cnt);
	for (; cnt > 0; -- cnt)
	{
		scanf("%d %d", &x, &y);
		C[x][y] = true;
	}
	f(1);
	printf("%d\n", ret);
	for (int i = 1; i < n; ++ i) if (!C[R[i]][R[i + 1]])
		printf("%d %d\n", R[i], R[i + 1]);
	for (int i = 1; i <= n; ++ i)
		printf("%d ", R[i]);

	return 0;
}