#include <stdio.h>
#include <string>
#include <vector>
#define nMax 520
using namespace std;
long n,m,i,j,a,b,p,q,dest,g[nMax],que[nMax],mark[nMax],ok[nMax];
long flux,last,d[nMax],list[nMax],v[nMax][nMax],f[nMax][nMax];
vector <int>r[nMax];

void edk(){
     long aux,i,p,q,st[nMax],t[nMax],mark[nMax];
     memset(mark,0,sizeof(mark));
     t[dest]=-1;t[0]=-1;mark[0]=1;
     st[1]=0;p=q=1;
     while (p<=q){
           for (i=0;i<g[st[p]];++i)
               if (!mark[v[st[p]][i]])
                 if (f[st[p]][v[st[p]][i]]){
                  st[++q]=v[st[p]][i];
                  mark[st[q]]=1;
                  t[st[q]]=st[p];
               }
           p++;
     }
     m=1;d[1]=dest;
     aux=t[dest];
     while (aux!=-1){
           d[++m]=aux;
           aux=t[aux];
     }
}
int main(){
    freopen("strazi.in","r",stdin);
    freopen("strazi.out","w",stdout);
    scanf("%ld %ld",&n,&m);
    //fie 0 sursa si 2n+1 destinatia
    for (i=1;i<=n;++i){v[0][g[0]++]=i;v[i][g[i]++]=0;f[0][i]=1;}
    for (i=1;i<=m;++i){
        scanf("%ld %ld",&a,&b);
        f[a][n+b]=1; v[a][g[a]++]=n+b; v[n+b][g[n+b]++]=a;
    }
    dest=n+n+1;
    for (i=1;i<=n;++i){v[n+i][g[n+i]++]=dest;v[dest][g[dest]++]=n+i;f[n+i][dest]=1;}
    //
    while(1){
       edk();if (m==1)break;
       flux++;
       for (i=1;i<m;++i){ f[d[i+1]][d[i]]--;f[d[i]][d[i+1]]++;}
    }
    printf("%ld\n",n-flux-1);
    for (i=n+1;i<=n+n;++i)
        for (j=1;j<=n;++j)
            if (f[i][j]){
               mark[j]++;mark[i-n]--;
               ok[i-n]=1;ok[j]=1;
               r[j].push_back(i-n);
            }
    last=0;m=0;
    for (i=1;i<=n;++i)
        if (mark[i]==1){
           que[1]=i;list[++m]=i;
           p=1;q=1;
           while (p<=q){
                 for (j=0;j<r[que[p]].size();++j){
                     que[++q]=r[que[p]][j];list[++m]=que[q];
                 }
                 p++;
           }
           if (last)printf("%ld %ld\n",last,que[1]);
           last=que[q];
        }
    for (i=1;i<=n;++i)if (!ok[i]){que[++q]=i;list[++m]=i;printf("%ld %ld\n",que[q-1],que[q]);}
    for (i=1;i<=n;++i)printf("%ld ",list[i]);
    printf("\n");
return 0;
}