#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

ifstream f("strazi.in");
ofstream g("strazi.out");

const int nmax = 260;
const int mmax = 300;
int n, m, z, i, x, y;
vector<int>ls[nmax];
int lft[nmax], rgt[nmax];
bool viz[nmax];
pair<int,int> sol[mmax];
int s2[nmax];

bool cuplu(int x) {
    if (viz[x]) return 0;
    int l = ls[x].size(), i,y;
    viz[x] = 1;
    for (i = 0; i < l; i++) {
        y = ls[x][i];
        if (rgt[y]==0) {
            lft[x] = y;
            rgt[y] = x;
            return 1;
        }
    }
    for (i = 0; i < l; i++) {
        y = ls[x][i];
        if (rgt[y] && cuplu(rgt[y])) {
            lft[x] = y;
            rgt[y] = x;
            return 1;
        }
    }

    return 0;
}

int main() {
    f >> n >> m;
    for (i = 1; i <= m; i++) {
        f >> x >> y;
        ls[x].push_back(y);
    }
    bool ok = 1;
    while (ok) {
        ok = 0;
        memset(viz,0,sizeof(viz));
        for (i = 1; i <= n; i++)
            if (lft[i] == 0)
                ok |= cuplu(i);
    }
    m = 0;
    for (i = 1; i <= n; i++) {
        if (rgt[i] == 0) {
            sol[++m] = make_pair(s2[z],i);
            s2[++z] = i;
            x = i;
            while (lft[x]) {
                s2[++z] = lft[x];
                x = lft[x];
            }
        }
    }
    g << m-1 << '\n';
    for (i = 2; i <= m; i++)
        g << sol[i].first << ' ' << sol[i].second <<'\n';
    for (i = 1; i <= n; i++)
        g << s2[i] << ' ';
    return 0;

}