#include<stdio.h>
#include<vector>

#define maxn 270
#define pb push_back

using namespace std;

FILE*f=fopen("strazi.in","r");
FILE*g=fopen("strazi.out","w");

int n,m;
int viz[maxn],L[maxn],R[maxn];
int Lant1[maxn],Lant2[maxn],lanturi;
vector<int>G[maxn];

int connect ( int nod ){
	if ( viz[nod] )	return 0;
	viz[nod] = 1;
	
	for ( vector<int>::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
		int nodvcn = (*itt);
		if ( !R[nodvcn] ){
			L[nod] = nodvcn; R[nodvcn] = nod;
			return 1;
		}
	}
	
	for ( vector<int>::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
		int nodvcn = (*itt);
		if ( connect(R[nodvcn]) ){
			L[nod] = nodvcn; R[nodvcn] = nod;
			return 1;
		}
	}
	
	return 0;
}

inline void cuplaj () {
	
	int ok = 0;
	do{
		for ( int i = 1 ; i <= n ; ++i ){
			viz[i] = 0;
		}
		
		ok = 0;
		for ( int i = 1 ; i <= n ; ++i ){
			if ( !L[i] ){
				ok |= connect(i);
			}
		}
	}while(ok);
}

inline void rezolva () {
	
	for ( int i = 1 ; i <= n ; ++i ){
		if ( !R[i] ){
			int nod = i;
			while ( L[nod] ){
				nod = L[nod];
			}
			++lanturi;
			Lant1[lanturi] = nod; Lant2[lanturi] = i;
		}
	}
	
	fprintf(g,"%d\n",lanturi-1);
	for ( int i = 1 ; i < lanturi ; ++i ){
		fprintf(g,"%d %d\n",Lant2[i],Lant1[i+1]);
		R[Lant2[i]] = Lant1[i+1];
	}
	int nod = Lant1[1];
	while ( nod ){
		fprintf(g,"%d ",nod);
		nod = R[nod];
	}
	fprintf(g,"\n");
}

int main () {
	
	fscanf(f,"%d %d",&n,&m);
	
	int x,y;
	for ( int i = 1 ; i <= m ; ++i ){
		fscanf(f,"%d %d",&x,&y);
		G[y].pb(x);
	}
	
	cuplaj();
	rezolva();
	
	fclose(f);
	fclose(g);
	
	return 0;
}