#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;
deque < int > path[maxN];

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)
        {
            Pair[i] -= n;
            if (onP[i])
            {
                if (i == path[onP[i]].back())
                {
                    path[onP[i]].push_back(Pair[i]);
                    onP[Pair[i]] = onP[i];
                }
            }
            else if (onP[Pair[i]])
            {
                if (Pair[i] == path[onP[Pair[i]]].front())
                {
                    path[onP[Pair[i]]].push_front(i);
                    onP[i] = onP[Pair[i]];
                }
            }
            else
            {
                onP[i] = onP[Pair[i]] = ++ nrp;
                path[nrp].push_front(i);
                path[nrp].push_back(Pair[i]);
            }
            ++ len;
        }
    for (int i = 1; i <= n; ++ i)
        if (Pair[i] == -1 && !onP[i])
            path[++ nrp].push_front(i);
    return len;
}
/* ------------------------------------------------------ */
void HamiltPath()
{
    for (int i = 1; i < nrp; ++ i)
        printf("%d %d\n", path[i].back(), path[i + 1].front());
    for (int i = 1; i <= nrp; ++ i)
        while (!path[i].empty())
        {
            printf("%d ", path[i].front());
            path[i].pop_front();
        }
}

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;
    printf("%d\n", nrp - 1);
    HamiltPath();

    return 0;
}