#include <cstdio>
#include <vector>
using namespace std;

#define Nmax 300

struct muchii {int x, y;} solM[Nmax];
int n, m;
int viz[Nmax], st[Nmax], dr[Nmax], solD[Nmax];
vector <int> V[Nmax];
void citire ();

int cuplaj (int nod) {
	
	if (viz[nod]) return 0;
	viz[nod] = 1;
	
	int i;
	for (i = 0 ; i < (int) V[nod].size (); i++) 
		if (!dr[ V[nod][i] ]) {
			dr[ V[nod][i] ] = nod;
			st[nod] = V[nod][i];
			return 1;
		}
	
	for (i = 0 ; i < (int) V[nod].size (); i++) 
		if (dr[ V[nod][i] ] && cuplaj ( dr[ V[nod][i] ] )) {
			dr[ V[nod][i] ] = nod;
			st[nod] = V[nod][i];
			return 1;
		}
	
	return 0;
}

int main () {

	freopen ("strazi.in", "r", stdin);
	freopen ("strazi.out", "w", stdout);
	
	citire ();
	
	int ok , i, N = 0, M = 0, nod;
	for (ok = 1; ok; ) {
		ok = 0;
		memset (viz, 0, sizeof (viz));
		
		for (i = 1; i <= n; i++)
			if (!st[i] && cuplaj (i)) 
				ok = 1;
	}
	
	for (i = 1; i <= n; i++) {
		if (!dr[i]) {
			solM[++M].x = solD[N]; solM[M].y = i;
			solD[++N] = i; viz[i] = 1;
			
			for (nod = i; st[nod]; nod = st[nod]) {
				solD[++N] = st[nod];
				viz[ st[nod] ] = 1;
			}
		}
	}

	printf ("%d\n", M-1);
	for (i = 2; i <= M; i++)
		printf ("%d %d\n", solM[i].x, solM[i].y);
	
	for (i = 1; i <= n; i++)
		printf ("%d ", solD[i]);

	return 0;
}

void citire () {
	
	int x, y, i;
	
	scanf ("%d %d", &n, &m);
	for (i = 1; i <= m; i++) {
		scanf ("%d %d", &x, &y);
		V[x].push_back (y);
	}
}