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

using namespace std;

const int MaxN = 300;

vector<int> G[MaxN], Begin;
int N, L[MaxN], R[MaxN], MaxMatching, End[MaxN];
bool V[MaxN];

int PairUp(int X) {
    if (V[X])
        return 0;
    V[X] = true;
    for (vector<int>::iterator Y = G[X].begin(); Y != G[X].end(); ++Y) {
        if (!L[*Y]) {
            R[X] = *Y, L[*Y] = X;
            return 1;
        }
    }
    for (vector<int>::iterator Y = G[X].begin(); Y != G[X].end(); ++Y) {
        if (PairUp(L[*Y])) {
            R[X] = *Y, L[*Y] = X;
            return 1;
        }
    }
    return 0;
}

void HopcroftKarp() {
    for (int Change = 1; Change; ) {
        Change = 0; memset(V, 0, sizeof(V));
        for (int X = 1; X <= N; ++X)
            if (!R[X])
                Change |= PairUp(X);
    }
    for (int X = 1; X <= N; ++X)
        MaxMatching += (R[X] != 0);
}

int DFS(int X) {
    if (!R[X])
        return X;
    return DFS(R[X]);
}

void Solve() {
    HopcroftKarp();
    for (int X = 1; X <= N; ++X)
        if (!L[X])
            Begin.push_back(X), End[X] = DFS(X);
    for (unsigned i = 0; i+1 < Begin.size(); ++i)
        R[End[Begin[i]]] = Begin[i+1];
}

void Read() {
    assert(freopen("strazi.in", "r", stdin));
    int M; assert(scanf("%d %d", &N, &M) == 2);
    for (; M; --M) {
        int X, Y; assert(scanf("%d %d", &X, &Y) == 2);
        G[X].push_back(Y);
    }
}

void PrintDFS(int X) {
    if (!X)
        return;
    printf("%d ", X);
    PrintDFS(R[X]);
}

void Print() {
    assert(freopen("strazi.out", "w", stdout));
    printf("%d\n", Begin.size()-1);
    for (int i = 0; i+1 < Begin.size(); ++i)
        printf("%d %d\n", End[Begin[i]], Begin[i+1]);
    PrintDFS(Begin[0]);
    printf("\n");
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}