#include <bits/stdc++.h>
#define Nmax 300
using namespace std;
ifstream f("strazi.in");
ofstream g("strazi.out");
struct graph
{
    int v1,v2;
};
graph muc[Nmax];
int n, m;
bool viz[Nmax];
int vL[Nmax];
int vR[Nmax];
int ans[Nmax];
list <int> G[Nmax];
bool cuplaj(int x)
{
    if(viz[x]) return false;
    viz[x]=true;
    for(list <int> :: iterator it=G[x].begin();it!=G[x].end();++it)
        if(!vL[*it] or cuplaj(vL[*it]))
        {
            vR[x]=*it;
            vL[*it]=x;
            return true;
        }
    return false;
}
int main ()
{
    f>>n>>m;
    int i,x,y,_n,_m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        G[x].push_back(y);
    }
    _n=_m=0;
    bool ok=true;
    while(ok)
    {
        ok=false;
        fill(viz+1,viz+n+1,false);
        for(i=1;i<=n;i++)
            if(!vR[i])
                if(cuplaj(i)) ok=true;
    }
    for(i=1;i<=n;i++)
    {
        if(!vL[i])
        {
            ++_m;
            muc[_m].v1=ans[_n];
            muc[_m].v2=i;
            ans[++_n]=i;
            viz[i]=true;
            x=i;
            while(vR[x])
            {
                ans[++_n]=vR[x];
                viz[vR[x]]=true;
                x=vR[x];
            }
        }
    }
    g<<_m-1<<'\n';
    for(i=2;i<=_m;i++)
        g<<muc[i].v1<<' '<<muc[i].v2<<'\n';
    for(i=1;i<=n;i++)
        g<<ans[i]<<' ';

    return 0;
}