#include<fstream>
#include<vector>
#include<string.h>
#include<algorithm>
#define dim 280
using namespace std;
 
ifstream f("strazi.in");
ofstream g("strazi.out");
vector< int >G[dim];
int uz[dim],l[dim],r[dim],n,m,i,cnt,change,Drum[dim],EndDrum,x,k,y;
void citire() { 
     
    f>>n>>m;
     
    for(i=1;i<=m;i++){
        f>>x>>y;
        G[x].push_back(y);
    }
     
}
int pairup(int x) {
     
    if(uz[x])
        return 0;
    uz[x]=1;
    int nod;
    for(int i=0;i<G[x].size();++i){
        nod=G[x][i];
        if(!r[nod] ){
            r[nod]=x;
            l[x]=nod;
            return 1;
        }
    }
    for(int i=0;i<G[x].size();++i){
        nod=G[x][i];
        if( r[nod]&& pairup(r[nod]) ){
            r[nod]=x;
            l[x]=nod;
            return 1;
        }
    }
    return 0;
}
void cuplaj () {
     
    change = 1 ;
     
    do{
         
        memset(uz,0,sizeof(uz));
        change = 0;
         
        for(i=1;i<=n;i++)
            if(!l[i])
                change|=pairup(i);
    }while(change);
     
    for(i=1;i<=n;i++)
        if(!l[i])
            ++cnt;
    g<<--cnt<<"\n";
     
}
void drum_hamiltonian() {
     
    for(i=1;i<=n;i++){
         
        if(!r[i]){
             
            if(EndDrum)
                g<<EndDrum<<" "<<i<<"\n";
             
            Drum[++k]=i;
             
            for(EndDrum=i;l[EndDrum];EndDrum=l[EndDrum])
                Drum[++k]=l[EndDrum];
             
        }
         
         
    }
     
    for(i=1;i<=k;i++)
        g<<Drum[i]<<" ";
}
int main () {
     
    citire ();
    cuplaj ();
    drum_hamiltonian();
     
    return 0;
}