using namespace std;
#include<cstdio>
#include<vector>
#define Nm 256
char Viz[Nm],ok=1;
int L[Nm],R[Nm],n,m;
vector<int> G[Nm],A[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(y);
    }
}

bool PairUp(int x)
{
    vector<int>::iterator it;
    
    Viz[x]=1;
    for(it=G[x].begin();it!=G[x].end();++it)
        if(!R[*it])
        {
            L[x]=*it;
            R[*it]=x;
            return ok=1;
        }
    for(it=G[x].begin();it!=G[x].end();++it)
        if(!Viz[R[*it]] && PairUp(R[*it]))
        {
            L[x]=*it;
            R[*it]=x;
            return ok=1;
        }
    return 0;
}

void solve()
{
    int i,x;

    while(ok)
    {
        memset(Viz+1,0,n*sizeof(char));
        for(ok=0,i=1;i<=n;++i)
            if(!L[i])
                PairUp(i);
    }

    m=0;
    for(i=1;i<=n;++i)
    {
        if(R[i])
            continue;
        ++m; x=i;
        do
        {
            A[m].push_back(x);
            x=L[x];
        }
        while(x);
    }
}

void write()
{
    int i;
    vector<int>::iterator it;
    
    freopen("strazi.out","w",stdout);
    printf("%d\n",m-1);
    for(i=1;i<m;++i)
        printf("%d %d\n",A[i].back(),A[i+1].front());
    for(i=1;i<=m;++i)
        for(it=A[i].begin();it!=A[i].end();++it)
            printf("%d ",*it);
}

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