#include <cstdio>
#include <vector>

using namespace std;

#define file_in "strazi.in"
#define file_out "strazi.out"

#define nmax (1<<8)

int N,M;
int a,b;
int ok,nr,nrr;
int i,j;
int Dr[nmax];
int St[nmax];
vector<int> G[nmax];
int viz[nmax];
int sol[nmax];

int cuplaj(int nod){
	
	vector<int> :: iterator it;
	
	if (viz[nod])
		return 0;
	
	viz[nod]=1;
	
	for (it=G[nod].begin();it!=G[nod].end();++it)
		 if (!St[*it]){
			 St[*it]=nod;
			 Dr[nod]=(*it);
			 return 1;
		 }
		 
	for (it=G[nod].begin();it!=G[nod].end();++it)
		 if (!viz[St[*it]] && cuplaj(St[*it])){
			 St[*it]=nod;
			 Dr[nod]=(*it);
			 return 1;
		 }	 
		 
	return 0;

}


int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &N, &M);
	while(M--){
		
		scanf("%d %d", &a, &b);
		G[a].push_back(b);
	}
	
	ok=1;
	nr=0;
	
	while(ok){
		
		ok=0;
		
		memset(viz,0,sizeof(viz));
		for (i=1;i<=N;++i)
			 if (Dr[i]==0 && cuplaj(i)){
				 nr++;
				 ok=1;
			 }
	}
	
	printf("%d\n", N-nr-1);
	
	ok=1;
	nrr=nr;
	nr=0;
    
	i=1;
	while(i<=N && St[i]) i++;
	St[i]=-1;   
    while (1) 
	{   
        while (Dr[i]) 
		{   
            sol[nr++]=i;   
            i=Dr[i];   
        }   
        sol[nr++]=i;   
        if (nrr+1>=N) 
			break;   
        j=1;
	    while(j<=N && St[j]) j++;
             Dr[i]=j;
 		     St[j]=i;   
        printf("%d %d\n", i, j);   
        i=j; 
		++nrr;   
    }   


	for (i=0;i<N;++i)
		 printf("%d ", sol[i]);
	
	return 0;
	
}