#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream f("strazi.in");
ofstream g("strazi.out");
vector <int> G[260];
int ind,ind2;
bool Use[260];
int L[260],R[260],ans;
int Road[260],N,M;
bool Matrix[260][260];
void Read()
{
    f>>N>>M;
    for(int i=1;i<=M;i++)
    {
        int x,y;
        f>>x>>y;
        G[x].push_back(y);
        Matrix[x][y]=1;
    }
}

bool pairup(int n)
{
    unsigned int i=0;
    if(Use[n]==1)
        return 0;
    Use[n]=1;
    for(i=0;i<G[n].size();i++)
    {
        int vecin=G[n][i];
        if(R[vecin]==0)
        {
            R[vecin]=n;
            L[n]=vecin;
            return 1;
        }
    }
    for(i=0;i<G[n].size();i++)
    {
        int vecin=G[n][i];
        if(pairup(R[vecin])==1)
        {
            R[vecin]=n;
            L[n]=vecin;
            return 1;
        }
    }
     return 0;
}
void Cuplaj()
{
    int i,cuplaj=0;
    bool change=1;
    while(change==1)
    {
        change=0;
        memset(Use,0,sizeof(Use));
        for(i=1;i<=N;i++)
            if(L[i]==0)
                change |=pairup(i);
    }
}

int DFS(int node)
{
    while(L[node]!=0)
    {
        Road[++Road[0]]=node;
        node=L[node];
    }
    Road[++Road[0]]=node;
    return node;
}
int main()
{
    Read();
    Cuplaj();
    for(int i=1;i<=N;i++)
        if(R[i]==0)
            DFS(i);
    for(int i=1;i<Road[0];i++)
    {
        if(Matrix[Road[i]][Road[i+1]]==0)
            ++ans;
    }
    g<<ans<<"\n";
    for(int i=1;i<Road[0];i++)
    {
        if(Matrix[Road[i]][Road[i+1]]==0)
            g<<Road[i]<<" "<<Road[i+1]<<"\n";
    }
    for(int i=1;i<=Road[0];i++)
        g<<Road[i]<<" ";
    g<<"\n";
    return 0;
}