#include <stdio.h>
#define NMax 256

int n, m, a[NMax][NMax], di[NMax], de[NMax], uz[NMax], used, l[NMax][NMax], p[NMax][NMax];
int in, sf, c[NMax];
int nd, lg[NMax], d[NMax][NMax];

void read();
void solve();
void write();
void calc_roads();
void delete_(int node);

int cost, v[NMax], cmin = 300, vmin[NMax];
void bkt(int p);
void writebk();

int main()
{
	read();
	if (n <= 10)
	{
		bkt(1);
		writebk();
	}
	else
	{
		solve();
		write();
	}
	return 0;
}

void calc_roads() // trebuie optimizat folosind liste de muchii
{
	int i, j, x;

	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
		{
			l[i][j] = -1;
			p[i][j] = -1;
		}

	for (i = 1; i <= n; i++)
		if (!uz[i])
		{
			in = sf = 0;
			c[0] = i;

			l[i][i] = 1;
			while (in <= sf)
			{
				x = c[in++];

				for (j = 1; j <= n; j++)
					if (a[x][j] && uz[j] == 0)
					{
						c[++sf] = j;
						l[i][j] = l[i][x] + 1;
						p[i][j] = x;
					}
			}
		}
}

int i;

void save_road(int st, int sf)
{
	while (st != sf)
	{
		d[nd][ lg[nd]++ ] = sf;
		uz[sf] = 1; used++;
		sf = p[st][sf];
	}
	d[nd][ lg[nd]++ ] = sf;
	uz[sf] = 1; used++;
	nd++;
}

void solve()
{
	int i, j, st, sf;

	while (used < n)
	{
		calc_roads();

		st = sf = -1;
		for (i = 1; i <= n; i++)
		{
			for (j = 1; j <= n; j++)
			{
				if (st == -1)
				{ st = i; sf = j; }
				
				if (l[i][j] > l[st][sf])
				{ st = i; sf = j; }
			}
		}
		save_road(st, sf);
	}
}

void write()
{
	int i, j;
	FILE *fout = fopen("strazi.out", "wt");

	fprintf(fout, "%d\n", nd - 1);

	for (i = 0; i < nd - 1; i++)
		fprintf(fout, "%d %d\n", d[i][0], d[i+1][lg[i+1]-1]);

	for (i = 0; i < nd; i++)
	{
		for (j = lg[i] - 1; j >= 0; j--)
			fprintf(fout, "%d ", d[i][j]);

	}
	fprintf(fout, "\n");
}


void read()
{
	int x, y;
	FILE *fin = fopen("strazi.in", "rt");

	fscanf(fin, "%d %d", &n, &m);
	while (m--)
	{
		fscanf(fin, "%d %d", &x, &y);
		de[x] ++;
		di[y] ++;
		a[x][y] = 1;
	}
}


void bkt(int p)
{
	if (p == n+1)
	{
		cost = 0;
		for (i = 1; i < n; i++)
			cost += (a[v[i]][v[i+1]] == 0);

		if (cost < cmin)
		{
			cmin = cost;
			for (i = 1; i <= n; i++)
				vmin[i] = v[i];
		}
	}
	else
	{
		for (v[p] = 1; v[p] <= n; v[p]++) if (uz[v[p]] == 0)
		{
			uz[v[p]] = 1;
			bkt(p+1);
			uz[v[p]] = 0;
		}
	}
}

void writebk()
{
	FILE *fout = fopen("strazi.out", "wt");

	fprintf(fout, "%d\n", cmin);

	for (i = 1; i < n; i++)
		if (a[vmin[i]][vmin[i+1]] == 0)
			fprintf(fout, "%d %d\n", vmin[i], vmin[i+1]);
	for (i = 1; i <= n; i++)
		fprintf(fout, "%d ", vmin[i]);

	fprintf(fout, "\n");
	fclose(fout);
}