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

#define pb push_back
#define nmax 255

using namespace std;
typedef pair<int, int> ii;

vector <ii> v;
int n, m, n1, n2, b[nmax], nb[nmax];
char a[nmax][nmax];

void solve()
{
	for(int i = 1; i <= n; i++) b[i] = i;
	int tot = 0, ntot, muvi = 0, muvj = 0;

	for(int i = 1; i < n; i++)
		if(a[b[i]][b[i + 1]]) tot++;

	for(int i = 1; i <= 300; i++)
	{
		int maxtot = tot;
		for(int i = 1; i <= n; i++)	
			for(int j = 1; j <= n + 1; j++)
			{
				ntot = tot + a[b[i - 1]][b[i + 1]] - a[b[i - 1]][b[i]] - a[b[i]][b[i + 1]] - a[b[j - 1]][b[j]] + a[b[j - 1]][b[i]] + a[b[i]][b[j]];
				if(ntot > maxtot)
				{
					maxtot = ntot;
					v.clear();
					v.pb(ii(i, j));
				}
				else if(ntot == maxtot) v.pb(ii(i, j));
			}
		if(v.size() == 0) return ;
		int x = rand() % v.size();
		muvi = v[x].first, muvj = v[x].second;
		for(int i = 1; i <= n; i++) nb[i] = b[i];
		for(int i = muvi; i < n; i++) nb[i] = nb[i + 1]; nb[n] = 0;
		if(muvj > muvi) muvj--;
		for(int i = n; i >= muvj; i--) nb[i] = nb[i - 1];
		nb[muvj] = b[muvi];
		for(int i = 1; i <= n; i++) b[i] = nb[i];
		tot = maxtot;
	}
}

int main()
{
	freopen("strazi.in", "r", stdin);
	freopen("strazi.out", "w", stdout);
	
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++)
	{
		scanf("%d%d", &n1, &n2);
		a[n1][n2] = 1;
	}
	solve();

	int tot = 0;
	for(int i = 1; i < n; i++) 
		if(!a[b[i]][b[i + 1]]) tot++;
	printf("%d\n", tot);

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

	return 0;
}