#include <cstdio>
#include <vector>
#include <bitset>
#define nmax 260
#define mmax 7010
using namespace std;
vector <int> v[nmax];
bitset <nmax> uz;
int n,m,sol,nr,t[nmax];
int l[nmax],r[nmax];

int cuplaj(int x)
{
    int i,y;
    uz[x]=1;
    for (i=0;i<v[x].size();i++) {
        y=v[x][i];
        if (r[y]==0) {
            l[x]=y;
            r[y]=x;
            return 1;
        }
    }
    for (i=0;i<v[x].size();i++) {
        y=v[x][i];
        if (uz[r[y]]==0&&cuplaj(r[y])) {
            l[x]=y;
            r[y]=x;
            return 1;
        }
    }
    return 0;
}
void recursion(int x)
{
    int y;
    if (nr==n)
        return;
    if (l[x]) {
        y=l[x];
        t[++nr]=y;
        uz[y]=1;
        recursion(y);
        return;
    }
    else {
        int i;
        for (i=1;i<=n;i++)
            if (uz[i]==0) {
                t[++nr]=i;
                uz[i]=1;
                printf("%d %d\n",x,i);
                recursion(i);
                return;
            }
    }
}
int main()
{
    freopen("strazi.in","r",stdin);
    freopen("strazi.out","w",stdout);
    int i,j,ok,x,y;
    scanf("%d %d",&n,&m);
    for (i=1;i<=m;i++) {
        scanf("%d %d",&x,&y);
        v[x].push_back(y);
    }
    do {
        uz.reset();
        ok=0;
        for (i=1;i<=n;i++)
            if (l[i]==0&&cuplaj(i))
                ok=1;
    } while (ok);

    for (i=1;i<=n;i++)
        if (l[i])
            sol++;
    printf("%d\n",n-sol-1);
    uz.reset();
    for (i=1;i<=n;i++)
        if (l[i]) {
            t[++nr]=i;
            uz[i]=1;
            recursion(i);
            break;
        }
    for (i=1;i<=n;i++)
        printf("%d ",t[i]);
    return 0;
}