#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define maxn 400

int n, m, i, j, k;
int cuplaj[maxn], viz[maxn], cuplat[maxn], a[maxn], b[maxn], d[maxn];
vector<int> v[maxn];

int cupleaza(int nod)
{
    int vecin;

    if(viz[nod])
        return 0;
    viz[nod]=1;

    for(int i=0; i<v[nod].size(); ++i)
    {
        vecin=v[nod][i];
        if(!cuplaj[vecin])
        {
            cuplat[nod]=1;
            cuplaj[vecin]=nod;
            return 1;
        }
    }

    for(int i=0; i<v[nod].size(); ++i)
    {
        vecin=v[nod][i];
        if(cuplaj[vecin]!=nod)
            if(cupleaza(cuplaj[vecin]))
            {
                cuplat[nod]=1;
                cuplaj[vecin]=nod;
                return 1;
            }
    }

    return 0;
}

int main()
{
    freopen("strazi.in", "r", stdin);
    freopen("strazi.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; ++i)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        v[b].push_back(a);
    }

    int ok=1, sol=n-1;
    while(ok)
    {
        ok=0;
        memset(viz, 0, sizeof(viz));
        for(int i=1; i<=n; ++i)
            if(cuplat[i]==0)
                if(cupleaza(i))
                {
                    --sol;
                    ok=1;
                }
    }

    printf("%d\n", sol);

    for(int i=1; i<=n; ++i)
        if(cuplat[i]==0)
            for(int j=i; j>0; j=cuplaj[j])
                d[++d[0]]=j;

    for(int i=1; i<n; ++i)
        if(cuplaj[d[i]]==0)
            printf("%d %d\n", d[i], d[i+1]);

    for(int i=1; i<=n; ++i)
        printf("%d ", d[i]);
    printf("\n");

    return 0;
}