#include <cstdio>
#include <vector>

using namespace std;

#define PB push_back

const int NMAX = 260;

vector <int> G[NMAX];
bool V[NMAX];
int N, M, st[NMAX], dr[NMAX], cu;

void read(void) {
	FILE *fin = fopen("strazi.in", "rt");
	int i, u, v;

	fscanf(fin, " %d %d", &N, &M);

	for (i = 0; i < M; ++i) {
		fscanf(fin, " %d %d", &u, &v);
		G[u].PB(v);
	}

	fclose(fin);
}

bool pair_up(int k) {
	if (V[k] == true) return false;
	V[k] = true;
	
	vector <int> :: iterator i;

	for (i = G[k].begin(); i != G[k].end(); ++i) {
		if (st[*i] == 0) {
			st[*i] = k;
			dr[k] = *i;
			++cu;
			return true;
		}
	}
	
	for (i = G[k].begin(); i != G[k].end(); ++i) {
		if (pair_up(st[*i])) {
			st[*i] = k;
			dr[k] = *i;			
			return true;
		}
	}
	
	return false;
}

void cuplaj(void) {
	bool ok;
	int i;
	
	cu = 0;
	do {
		ok = false;
		memset(V, 0x00, sizeof(V));
		for (i = 1; i <= N; ++i)
			if (dr[i] == 0)
				ok |= pair_up(i);
	} while (ok);
}

void write(void) {
	FILE *fout = fopen("strazi.out", "wt");
	int i, j;
	int sol[NMAX], NS = 0;

	cuplaj();

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

	for (i = 1; i <= N && st[i]; ++i);
	st[i] = -1;
	while (1) {
		while (dr[i]) {
			sol[NS++] = i;
			i = dr[i];
		}
		sol[NS++] = i;
		if (cu + 1 >= N) break;
		for (j = 1; j <= N && st[j]; ++j);
		dr[i] = j; st[j] = i;
		fprintf(fout, "%d %d\n", i, j);
		i = j; ++cu;
	}

	for (i = 0; i < N; ++i)
		fprintf(fout, "%d ", sol[i]);
	fprintf(fout, "\n");

	fclose(fout);
}

int main(void) {

	read();

	write();

	return 0;
}