#include <stdio.h>
#include <vector>
#define INF (1 << 30)

using namespace std;

int C[600][600], F[600][600], TT[600], hamilton[600], used[600];
vector <int> G[600];

inline bool BFS(int N)
{
    int i, p, u, vis[600], Q[600];
    vector <int> :: iterator it;

    for (i = 1; i <= N; i ++)
        vis[i] = 0;
    vis[0] = 1;
    p = u = 1; Q[1] = 0; TT[0] = -1;

    while (p <= u)
    {
        int nod = Q[p];

        for (it = G[nod].begin(); it != G[nod].end(); it ++)
            if (F[nod][*it] < C[nod][*it] && !vis[*it])
            {
                TT[*it] = nod;
                vis[*it] = 1;
                Q[++ u] = *it;
            }

        p ++;
    }

    return vis[N];
}

void augment(int N)
{
    int nod = N;

    while (TT[nod] != -1)
    {
        F[TT[nod]][nod] ++;
        F[nod][TT[nod]] --;
        nod = TT[nod];
    }
}

void DFS(int nod, int N)
{
    vector <int> :: iterator it;

    hamilton[++ hamilton[0]] = nod;
    used[nod] = 1;

    for (it = G[nod].begin(); it != G[nod].end(); it ++)
        if (F[nod][*it])
            DFS(*it - N, N);
}

int main()
{
    int i, N, M;

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

    scanf("%d%d", &N, &M);
    for (i = 1; i <= M; i ++)
    {
        int x0, y0;

        scanf("%d%d", &x0, &y0);
        G[x0].push_back(y0 + N);
        C[x0][y0 + N] = 1;
    }
    for (i = 1; i <= N; i ++)
    {
        C[0][i] = 1;
        G[0].push_back(i);
        C[i + N][2 * N + 1] = 1;
        G[i + N].push_back(2 * N + 1);
    }

    int cover = 0;

    while (BFS(2 * N + 1))
    {
        ++ cover;
        augment(2 * N + 1);
    }

    printf("%d\n", N - cover - 1);

    for (i = 1; i <= N; i ++)
        if (!used[i])
            DFS(i, N);

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

    return 0;
}