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

using namespace std;

vector<int> v[256];
int mat[256][256], sol, nr, n, m, used[256], chain[256], finalchain[256], cnt;
vector<pair<int, int> > p, finalp;

void bkt(int);
void dfs(int);

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

	int i, a, b;

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

	for(i = 1; i <= m; ++i)
	{
		scanf("%d %d", &a, &b);
		v[a].push_back(b);
		mat[a][b] = 1;
	}
	for(i = 1; i <= n; ++i)
	{
		mat[0][i] = 1;
		v[0].push_back(i);
	}

	if(n <= 10)
	{
		sol = n;
		bkt(1);
	}
	else
	{
		cnt = n;
		dfs(0);
		sol = 0;
		for(i = 1; i < n; ++i)
		{
			if(!mat[finalchain[i]][finalchain[i + 1]])
			{
				++sol;
				finalp.push_back(make_pair(finalchain[i], finalchain[i +1]));
			}
		}			
	}

	printf("%d\n", sol);
	for(i = 0; i < sol; ++i)
	{
		printf("%d %d\n", finalp[i].first, finalp[i].second);
	}
	for(i = 1; i <= n; ++i)
	{
		printf("%d ", finalchain[i]);
	}


	return 0;
}

void bkt(int k)
{
	if(k == n + 1)
	{
		if(nr < sol)
		{
			sol = nr;
			int i, sz = p.size();
			finalp.clear();
			for(i = 0; i < sz; ++i)
			{
				finalp.push_back(p[i]);
			}
			for(i = 1; i <= n; ++i)
			{
				finalchain[i] = chain[i];
			}
		}
	}
	else
	{
		int i;
		for(i = 1; i <= n; ++i)
		{
			if(!used[i])
			{
				chain[k] = i;
				used[i] = 1;
				if(!mat[chain[k - 1]][chain[k]])
				{
					++nr;
					p.push_back(make_pair(chain[k - 1], chain[k]));
				}
				bkt(k + 1);
				used[i] = 0;	
				if(!mat[chain[k - 1]][chain[k]])
				{
					--nr;
					p.pop_back();
				}
			}	
		}
	}
}

void dfs(int nod)
{
	int i, sz = v[nod].size();
	used[nod] = 1;
	for(i = 0; i < sz; ++i)
	{
		if(!used[v[nod][i]])
		{
			dfs(v[nod][i]);
		}
	}
	finalchain[cnt] = nod;
	--cnt;
}