#include<fstream>
#include<vector>

using namespace std;

const char iname[]="strazi.in";
const char oname[]="strazi.out";
const int maxn=260;

ifstream f(iname);
ofstream g(oname);

vector<int> E[maxn];
int n,ans[maxn][2],x,y,been[maxn],l[maxn],r[maxn],i,m,k,rez[maxn],ok,j;

int go(int x)
{
    if(been[x])
        return 0;
    been[x]=1;
    for(vector<int>::iterator it=E[x].begin();it!=E[x].end();++it)
        if(r[*it]==0)
        {
            r[*it]=x;
            l[x]=*it;
            return 1;
        }
    for(vector<int>::iterator it=E[x].begin();it!=E[x].end();++it)
        if(go(r[*it]))
        {
            r[*it]=x;
            l[x]=*it;
            return 1;
        }
    return 0;
}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
        f>>x>>y,E[x].push_back(y);
    do
    {
        ok=0;
        memset(been,0,sizeof(been));
        for(i=1;i<=n;++i)
            if(!l[i])
                ok|=go(i);
    }while(ok);
    m=0;
    for(i=1;i<=n;++i)
        if(!r[i])
        {
            ans[++m][0]=j;ans[m][1]=i;
            rez[++k]=i;
            for(j=i;l[j];j=l[j])
                rez[++k]=l[j];
        }
    g<<m-1<<"\n";
    for(i=2;i<=m;++i)
        g<<ans[i][0]<<" "<<ans[i][1]<<"\n";
    for(i=1;i<=k;++i)
        g<<rez[i]<<" ";
    g<<"\n";
}