#include <stdio.h>
#include <vector>

using namespace std;

#define nm 256

int n, m, mat[nm][nm], used[nm], sol = 1000;
vector <int> v, p, r;

void go(int pos)
{
	if (pos > n) {
		vector <int> crt;

		for (int i = 0; i < n - 1; ++i)
			if (!mat[v[i]][v[i + 1]])
				crt.push_back(i);

		if (sol > (int)crt.size()) {
			sol = crt.size();
			
			p = v;
			r = crt;
		}
	} else {
		for (int i = 1; i <= n; ++i)
			if (!used[i]) {
				v.push_back(i);
				used[i] = 1;
				go(pos + 1);
				used[i] = 0;
				v.pop_back();
			}
	}
}

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

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

	for (int i = 1; i <= m; ++i) {
		int x, y;

		scanf("%d%d", &x, &y);
		mat[x][y] = 1;
	}

	go(1);

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

	for (int i = 0; i < sol; ++i)
		printf("%d %d\n", p[r[i]], p[r[i] + 1]);

	for (int i = 0; i < n; ++i)
		printf("%d ", p[i]);
	printf("\n");

	return 0;
}