using namespace std;
#include<cstdio>
#include<cstring>
#include<vector>
#define Nm 256
int Match[Nm<<1],X[Nm],Y[Nm],P[Nm],n,e;
int Q[Nm<<1],Dm[Nm<<1],Viz[Nm<<1],d;
vector<int> G[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(n+y);
    }
}

int BFS()
{
    int l=0,r=-1,i,x;
    vector<int>::iterator it;

    d=0;
    memset(Dm,0,sizeof(Dm));
    for(i=1;i<=n;++i)
        if(!Match[i])
        {
            Q[++r]=i;
            Dm[i]=1;
        }

    while(l<=r)
    {
        x=Q[l++];
        if(x>n)
        {
            if(Match[x])
            {
                Q[++r]=Match[x];
                Dm[Match[x]]=Dm[x]+1;
            }
            else
                if(!d) d=Dm[x];
            continue;
        }

        for(it=G[x].begin();it!=G[x].end();++it)
            if(!Dm[*it])
            {
                Q[++r]=*it;
                Dm[*it]=Dm[x]+1;
            }
    }
    return d;
}

bool DFS(int x)
{
    Viz[x]=1;
    if(Dm[x]==d)
        return !Match[x];
    if(x>n)
        return DFS(Match[x]);

    vector<int>::iterator it;
    
    for(it=G[x].begin();it!=G[x].end();++it)
        if(!Viz[*it] && Dm[*it]==Dm[x]+1 && DFS(*it))
        {
            Match[x]=*it;
            Match[*it]=x;
            return 1;
        }
    return 0;
}

void path(int x)
{
    Viz[x]=1;
    if(Match[n+x] && !Viz[Match[n+x]])
        path(Match[n+x]);
    P[d++]=x;
    if(Match[x] && !Viz[Match[x]-n])
        path(Match[x]-n);
}

void solve()
{
    int i,j;
    vector<int>::iterator it;

    for(i=1;i<=n;++i)
        for(it=G[i].begin();it!=G[i].end();++it)
            if(!Match[*it])
            {
                Match[i]=*it;
                Match[*it]=i;
                break;
            }

    while(BFS())
    {
        memset(Viz,0,sizeof(Viz));
        for(i=1;i<=n;++i)
            if(!Match[i])
                DFS(i);
    }

    d=0; e=0;
    memset(Viz,0,sizeof(Viz));
    path(1);
    for(i=2;i<=n;++i)
        if(!Viz[i])
        {
            j=d;
            path(i);
            X[e]=P[j-1];
            Y[e++]=P[j];
        }
}

void write()
{
    int i;

    freopen("strazi.out","w",stdout);
    printf("%d\n",e);
    for(i=0;i<e;++i)
        printf("%d %d\n",X[i],Y[i]);
    for(i=0;i<n-1;++i)
        printf("%d ",P[i]);
    printf("%d\n",P[i]);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}