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

using namespace std;

#define maxn 256
#define pb push_back

int n, m, draw, sol, rez, l;
vector <int> a[maxn];
int g[maxn];
int mark[maxn], u[maxn], c[maxn];
int v[maxn], s[maxn];

int DFS(int nod)
{
	if (u[nod] == draw) return 0;

	int i;
	u[nod] = draw;

	for (i=0; i<g[nod]; i++)
		if (mark[a[nod][i]] == -1 || DFS(mark[a[nod][i]]))
		{
			mark[a[nod][i]] = nod;
			return 1;
		}

	return 0;
}

int cuplaj()
{
	int rez = 0, i;
	memset(mark, -1, sizeof(mark));
	
	for (i=1; i<=n; i++)
	{
		draw++;
		rez += DFS(i);
	}

	return rez;
}

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

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

	int i, x, y;

	for (i=1; i<=m; i++)
	{
		scanf("%d %d ", &x, &y);
		a[x].pb(y);
	}

	for (i=1; i<=n; i++) g[i] = a[i].size();

	sol = n - 1 - cuplaj();

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

	memset(c, -1, sizeof(c));

	for (i=1; i<=n; i++)
		if (mark[i] != -1) c[mark[i]] = i;
		else v[++l] = i;

	for (i=1; i<l; i++)
	{
		x = v[i];
		while (c[x] != -1) x = c[x];

		printf("%d %d\n", x, v[i+1]);
		c[x] = v[i+1];
	}

	x = v[1];
	for (i=1; i<=n; i++) 
	{
		printf("%d ", x);
		x = c[x];
	}

	printf("\n");

	return 0;
}