using namespace std;  
 #include<cstdio>  
 #include<vector>  
 #define Nm 256  
 char Viz[Nm],ok=1;  
 int L[Nm],R[Nm],n,m;  
 vector<int> G[Nm],A[Nm];  
   
 void read()  
 {  
     int m,x,y;  
   
     freopen("strazi.in","r",stdin);  
     scanf("%d%d",&n,&m);  
     while(m--)  
     {  
         scanf("%d%d",&x,&y);  
         G[x].push_back(y);  
     }  
 }  
   
 bool PairUp(int x)  
 {  
     vector<int>::iterator it;  
       
     Viz[x]=1;  
     for(it=G[x].begin();it!=G[x].end();++it)  
         if(!R[*it])  
         {  
             L[x]=*it;  
             R[*it]=x;  
             return ok=1;  
         }  
     for(it=G[x].begin();it!=G[x].end();++it)  
         if(!Viz[R[*it]] && PairUp(R[*it]))  
         {  
             L[x]=*it;  
             R[*it]=x;  
             return ok=1;  
         }  
     return 0;  
 }  
   
 void solve()  
 {  
     int i,x;  
   
     while(ok)  
     {  
         memset(Viz+1,0,n*sizeof(char));  
         for(ok=0,i=1;i<=n;++i)  
             if(!L[i])  
                 PairUp(i);  
     }  
   
     m=0;  
     for(i=1;i<=n;++i)  
     {  
         if(R[i])  
             continue;  
         ++m; x=i;  
         do  
         {  
             A[m].push_back(x);  
             x=L[x];  
        }  
         while(x);  
     }  
 }  
   
 void write()  
 {  
    int i;  
     vector<int>::iterator it;  
       
     freopen("strazi.out","w",stdout);  
     printf("%d\n",m-1);  
     for(i=1;i<m;++i)  
         printf("%d %d\n",A[i].back(),A[i+1].front());  
     for(i=1;i<=m;++i)  
         for(it=A[i].begin();it!=A[i].end();++it)  
             printf("%d ",*it);  
 }  
   
 int main()  
 {  
     read();  
     solve();  
     write();  
     return 0;  
}