#include <bits/stdc++.h>
#define maxN 257
using namespace std;

FILE *fin = freopen("strazi.in", "r", stdin);
FILE *fout = freopen("strazi.out", "w", stdout);

/* --------------------------------- */
int n, m;
vector < int > V[2 * maxN];
/* ---------------- Match data ----------------- */
int Pair[2 * maxN];
bool vis[2 * maxN];
/* --------------------------------- */
int onP[maxN], nrp;
vector < int > Path;

int ans;

/* ---------------- Matching ---------------- */
bool PairUp(int x)
{
    if (vis[x])
        return 0;
    vis[x] = 1;
    for (int y : V[x])
        if (Pair[y] == -1 || PairUp(Pair[y]))
        {
            Pair[x] = y;
            Pair[y] = x;
            return 1;
        }
    return 0;
}
int Match()
{
    int len = 0;
    for (int i = 1; i <= 2 * n; ++ i)
        Pair[i] = -1;

    bool ok = 0;
    do
    {
        ok = 0;
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; ++ i)
            if (Pair[i] == -1)
                ok |= PairUp(i);
    }
    while (ok);

    for (int i = 1; i <= n; ++ i)
        if (Pair[i] != -1)
            ++ len;
    return len;
}
int dfs(int x)
{
    vis[x] = 1;
    Path.push_back(x - n);
    if (Pair[x - n] == -1)
        return x - n;
    return dfs(Pair[x - n]);
}

/* ------------------------------------------------------ */
void HamiltPath()
{
    int bck = -1;
    printf("%d\n", ans);

    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; ++ i)
        if (Pair[i + n] == -1 && !vis[i])
        {
            if (bck != -1)
                printf("%d %d\n", bck, i);
            bck = dfs(i + n);
        }

    for (int i = 0; i < n; ++ i)
        printf("%d ", Path[i]);
}

int main()
{
    scanf("%d %d", &n, &m);
    while (m --)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        V[x].push_back(y + n);
    }

    ans = n - Match() - 1;
    HamiltPath();

    return 0;
}