#include <stdio.h>
#include <vector>
using namespace std;

#define NMAX 550
#define INF 10000

int N, M, beg, end, beg1, end1;

vector <int> leg[NMAX];
int cap[NMAX][NMAX];
int flux[NMAX][NMAX];

int xx[7010];
int yy[7010];

int pred[NMAX];
int coada[NMAX];
char viz[NMAX];
int mn[NMAX];

int out[NMAX];
int in[NMAX];

int fin[NMAX];

inline int MIN(int a, int b) { return (a < b) ? a : b; }

int bf(int beg, int end)
{
	int p = 0, q = 0, x, y;
	memset(viz, 0, sizeof(viz));
	memset(pred, 0, sizeof(pred));
	memset(mn, 0, sizeof(mn));

	coada[0] = beg;
	viz[beg] = 1;
	mn[beg] = INF;

	while (p <= q) {
		x = coada[p];
		p++;

		for (vector <int> :: iterator it = leg[x].begin(); it != leg[x].end(); ++it) {
			y = *it;

			if (!viz[y] && flux[x][y] < cap[x][y]) {
				viz[y] = 1;
				coada[++q] = y;
				mn[y] = MIN(mn[x], cap[x][y] - flux[x][y]);
				pred[y] = x;

				if (y == end) return 1;
			}
		}
	}

return 0;
}

void baga_flux(int beg, int end)
{
	int cur, fl;
	while (bf(beg, end)) {
		cur = end;
		fl = mn[end];

		while (cur != beg) {
			flux[pred[cur]][cur] += fl;
			flux[cur][pred[cur]] -= fl;
			cur = pred[cur];
		}
	}
}

int main()
{
	int i, x, y;

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

	scanf("%d %d", &N, &M);

	beg = 0, end = 2 * N + 1;
	beg1 = 2 * N + 2; end1 = 2 * N + 3;

	for (i = 1; i <= N; i++) {
		leg[i].push_back(N + i);
		leg[N + i].push_back(i);

		leg[beg].push_back(i);
		leg[i].push_back(beg);
		leg[N + i].push_back(end);
		leg[end].push_back(N + i);

		cap[beg][i] = INF;
		cap[N + i][end] = INF;
	}

	for (i = 1; i <= M; i++) {
		scanf("%d %d", &x, &y);

		xx[i] = x; yy[i] = y;

		leg[N + x].push_back(y);
		leg[y].push_back(N + x);

		cap[N + x][y] = INF;
	}

	leg[beg].push_back(end);
	leg[end].push_back(beg);
	cap[beg][end] = cap[end][beg] = INF;

	// sursa si destinatia 2
	
	for (i = 1; i <= N; i++) {
		leg[beg1].push_back(N + i);
		cap[beg1][N + i] = 1;

		leg[i].push_back(end1);
		cap[i][end1] = 1;
	}

	baga_flux(beg1, end1);
	baga_flux(end, beg);

	int rez = 0;
	for (i = 1; i <= N + N; i++) 
		if (flux[i][end] > 0) rez += flux[i][end];

	printf("%d\n", rez - 1);

	for (i = 1; i <= M; i++) {
		x = xx[i]; y = yy[i];

		if (flux[N + x][y] == 1) out[x] = y, in[y] = x;
	}

	int q;
	for (i = 1; i <= N; i++) {
		if (in[i]) continue;

		if (fin[0]) printf("%d %d\n", fin[fin[0]], i);

		q = i;
		while (q) {
			fin[++fin[0]] = q;
			q = out[q];
		}
	}

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

return 0;
}