#include <iostream>

#define FIN "strazi.in"
#define FOUT "strazi.out"
#define MAXN 256

int n, m, cupl;
struct item { int nod; item *r; } *L[MAXN];
int X[MAXN], Y[MAXN], Used[MAXN]; // cine cu cine e cuplat

int cupleaza(int x)
{
    int i;
    if (Used[x]) return 0;
    Used[x] = 1;
    for (item *p = L[x]; p; p = p->r) {
        if ( !Y[p->nod] || cupleaza(Y[p->nod]) ) {
            X[x] = p->nod;
            Y[p->nod] = x;
            ++cupl;
            return 1;
        }
    }
    return 0;
}

int main()
{
    int x, y;
    freopen(FIN, "r", stdin);
    freopen(FOUT,"w",stdout);
    scanf("%d %d", &n, &m);
    while (m--) {
        scanf("%d %d", &x, &y);
        item *p = new item;
        *p = (item) { y, L[x] };
        L[x] = p;
    }
    for (x=1; x<=n; ++x) {
        if (!X[x] && !cupleaza(x)) {
            memset(Used, 0, sizeof(Used));
            cupleaza(x);
        }
    }
    printf("%d\n", n-cupl-1);
    for (x=1; x<=n && Y[x] != 0; ++x) ; // gasesc primul inceput de drum
    while (cupl+1 < n) {
        Y[x] = -1; // to avoid cycles
        for (; X[x]; x = X[x]) ;
        for (y=1; y<=n; ++y) {
            if (Y[y] == 0 && y != x) {
                X[x] = y; // leg si in graful bipartit...
                ++cupl;
                printf("%d %d\n", x, y);
                x = y;
                break;
            }
        }
    }
    for (x=1; x<=n; ++x) {
        if (Y[x] <= 0) {
            printf("%d", x);
            while (X[x]) {
                printf(" %d", x = X[x]);
            }
            break;
        }
    }
    printf("\n");
    return 0;
}