#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

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

#define Nmax 260
#define Inf 0x3f3f3f3f
#define pb push_back

vector<int> v[Nmax];
int n,m,x,y;
int viz[Nmax];
int ok,nr;
int st[Nmax];
int dr[Nmax];
int sol[Nmax];


bool cuplaj(int nod)
{
	vector<int> :: iterator it;
	
	if (viz[nod]) return false;
	
	viz[nod]=1;
	
	for (it=v[nod].begin();it<v[nod].end();++it)
	    if (!st[*it])
	    {
			st[*it]=nod;
		    dr[nod]=*it;
		    return true;
	    }
	
	for (it=v[nod].begin();it<v[nod].end();++it)
	    if (!viz[*it] && cuplaj(st[*it]))   
	    {
			st[*it]=nod;
		    dr[nod]=*it;
		    return true;
	    }
		
	return false;
}	
			
			
int main()
{
	int i,j;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n,&m);
	for (i=1;i<=m;++i)
	{
		scanf("%d %d", &x,&y);
		v[x].pb(y);
	}
	
	ok=1;
	nr=0;
	
	while(ok)
	{
		ok=0;
		memset(viz,0,sizeof(viz));
		
		for (i=1;i<=n;++i)
			 if (!dr[i] && cuplaj(i))
			 {
				 ok=1;
				 nr++;
			 }
	}
	
	printf("%d\n", n-nr-1);
	
	ok=1;
	//nr=0;
	int nrr;
	nrr=nr;
	nr=0;
    
	for (i=1;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;   
        for (j=1;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]);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}