#include <cstdio>
#include <cstring>

const int Nmax = 256;

int N;
char A[Nmax][Nmax];

char viz[Nmax];
int Cuplat[Nmax];
char mark[Nmax];

int Ret;
int N1[Nmax], N2[Nmax];

void ReadData() {
	freopen("strazi.in", "r", stdin);
	freopen("strazi.out", "w", stdout);
	
	int M;
	for (scanf("%d %d", &N, &M); M; --M) {
		int a, b; scanf("%d %d", &a, &b);
		A[a][b] = 1;
	}
}

int Cupleaza(int nod) {
	if (viz[nod] == 1) return 0;
	viz[nod] = 1;
	
	for (int i = 1; i <= N; ++i)
		if (A[nod][i])
			if (!Cuplat[i] || Cupleaza(Cuplat[i])) {
				Cuplat[i] = nod;
				return 1;
			}
	return 0;
}

void Bipartite_Matching() {
	for (int i = 1; i <= N; ++i) {
		memset(viz, 0, sizeof(viz));
		mark[i] = Cupleaza(i);
	}
}

int DF(int nod) {
	if (!Cuplat[nod]) return nod;
	return DF(Cuplat[nod]);
}

void Solve() {
	Bipartite_Matching();
	for (int i = 1; i <= N; ++i)
		if (!mark[i]) {
			++Ret;
			N1[Ret] = i;
			N2[Ret] = DF(i);
		}
}

void DF2(int nod) {
	if (Cuplat[nod]) DF2(Cuplat[nod]);
	printf("%d ", nod);
}

void WriteData() {
	printf("%d\n", Ret-1);
	for (int i = 1; i < Ret; ++i) {
		printf("%d %d\n", N1[i], N2[i+1]);
		Cuplat[N2[i+1]] = N1[i];
	}
	DF2(N2[Ret]);
}

int main() {
	ReadData();
	Solve();
	WriteData();
}