#include <vector>
#include <cstring>
#include <cstdio>

using namespace std;

const int nmax = 260;
int L[nmax];
int R[nmax];
bool U[nmax];
int M[nmax][nmax];
vector<int> A[nmax];
int n, m;

bool pairup(int x) {
    if (U[x])
        return false;
    U[x] = 1;
    for (int i = 0; i < A[x].size(); i++) {
        int y = A[x][i];
        if (!R[y] || pairup(R[y])) {
            L[x] = y;
            R[y] = x;
            return true;
        }
    }

    return false;
}

void cuplaj() {
    bool ok = true;
    while (ok) {
        ok = false;
        memset(U, 0, sizeof(U));
        for (int i = 1; i <= n; i++) {
            if (!L[i] && pairup(i))
                ok = true;
        }
    }
}

vector<pair<int, int> > ans;
vector<int> path;

void find_path(int x) {
    if (path.size() != 0 && M[path.back()][x] == 0)
        ans.push_back(make_pair(path.back(), x));
    path.push_back(x);
    if (L[x]) {
        find_path(L[x]);
    }
}

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

    scanf("%d %d", &n, &m);

    for (int i = 1, x, y; i <= m; i++) {
        scanf("%d %d", &x, &y);
        A[x].push_back(y);
        M[x][y] = 1;
    }

    cuplaj();

    for (int i = 1; i <= n; i++) {
        if (!R[i]) {
            find_path(i);
        }
    }

    printf("%d\n", ans.size());
    for (int i = 0; i < ans.size(); i++) {
        printf("%d %d\n", ans[i].first, ans[i].second);
    }

    for (int i = 0; i < path.size(); i++) {
        printf("%d ", path[i]);
    }
    printf("\n");

    return 0;
}