#include <stdio.h>
#include <vector>
#define Nmax 255+2
#define Mmax 7000+2
#define pb push_back

using namespace std;

vector< int > v[Nmax];
int L[Nmax],R[Nmax],use[Nmax],vf[Nmax];
int N,M;

int cupleaza(int i){
	vector< int >:: iterator it;
	use[i]=1;
	
	for(it=v[i].begin(); it!=v[i].end(); ++it)
		if( !R[*it] || ( !use[R[*it]] && cupleaza(R[*it]) )){
			L[i]=*it; R[*it]=i;
			return 1;
		}
	return 0;
}

int main(){
	int i,still,x,y,nr=0,end=0;
	freopen("strazi.in","r",stdin);
	freopen("strazi.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(i=1;i<=M;++i){
		scanf("%d%d",&x,&y);
		v[x].pb(y);
	}
	
	for( still=1; still; ){
		still=0;
		memset(use,0,sizeof(use));
		for(i=1;i<=N;++i)
			if( !L[i] && cupleaza(i) )
				still=1;
	}
	
	for(i=1;i<=N;++i) 
		if( ! L[i] ) ++nr;
	printf("%d\n",--nr);
	
	for(i=1;i<=N;++i)
		if( ! R[i] ){
			if( end ) printf("%d %d\n",end,i);
			vf[++vf[0]]=i;
			for( end=i; L[end]; end=L[end] )
				vf[++vf[0]]=L[end];
		}

	for(i=1; i<vf[0]; ++i)
		printf("%d ",vf[i]);
	printf("%d\n",vf[vf[0]]);
	
	fclose(stdin); fclose(stdout);
	return 0;
}