#include <fstream>
#include <vector>
#include <bitset>

#define DIM 256

using namespace std;

ifstream fin("strazi.in");
ofstream fout("strazi.out");

bitset<DIM>X[DIM];

vector<int> L[DIM];

bitset<DIM>v;

int drum[DIM], stanga[DIM], dreapta[DIM];

int n, m, a, b, k, ok, nr;

bool cuplaj(int nod)
{
    v[nod] = 1;

    for(int i = 0; i < L[nod].size(); i ++)
    {
        int a = L[nod][i];
        if(dreapta[a] == 0)
        {
            stanga[nod] = a;
            dreapta[a] = nod;
            return true;
        }
    }
    for(int i = 0; i < L[nod].size(); i ++)
    {
        int a = L[nod][i];
        if(cuplaj(dreapta[a]) && v[dreapta[a]] == 0 )
        {
            dreapta[a] = nod;
            stanga[nod] = a;
            return true;
        }
    }

    return false;
}

void dfs(int nod){

    drum[++k] = nod;

    if(stanga[nod] == 1)
        dfs(stanga[nod]);

}

int main()
{
    fin >> n >> m;

    for(int i = 1; i <= m; i ++)
    {
        fin >> a >> b;
        L[a].push_back(b);
        X[a][b] = 1;
    }

    while(1)
    {
        ok = 0;
        for(int i = 1; i <= n; i ++)
        {
            v[i] = 0;
        }
        for(int i = 1; i <= n; i ++)
        {
            if( cuplaj(i) == 1 && stanga[i] == 0 )
            {
                nr ++;
                ok = 1;
            }
        }

        if(ok == 0)
            break;
    }

    fout << n - 1 - nr << '\n';

    for(int i = 1; i <= n; i ++)
    {
        if(dreapta[i] == 0)
        {
            dfs(i);
        }
    }

    for(int i = 1; i < k; i ++)
    {
        if(X[drum[i]][drum[i + 1]] == 1)
        {
            fout << drum[i] << " " << drum[i + 1] << '\n';
        }
    }

    for(int i = 1; i <= k; i ++)
    {
        fout << drum[i] << " ";
    }

    return 0;
}