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

using namespace std;

const int kMaxN = 300;

int n;
int m;
int matchLef[kMaxN];
int matchRig[kMaxN];
vector <int> G[kMaxN];
bool seen[kMaxN];

bool findPair(const int u) {
    if (seen[u] == false) {
        seen[u] = true;
        for (const int v: G[u]) {
            if (matchRig[v] == 0) {
                matchLef[u] = v;
                matchRig[v] = u;
                return true;
            }
        }
        for (const int v: G[u]) {
            if (findPair(matchRig[v]) == true) {
                matchLef[u] = v;
                matchRig[v] = u;
                return true;
            }
        }
        return false;
    }
    else return false;
}

void matchMaximum() { 
    bool isComplete = false;
    do {
        isComplete = true;
        memset(seen, 0, sizeof seen);
        for (int i = 1; i <= n; i++) {
            if (matchLef[i] == 0 && findPair(i) == true) {
                isComplete = false;
            }
        }
    } while (isComplete == false);
}

vector <vector <int>> findCover() {
    vector <vector <int>> c;
    memset(seen, 0, sizeof seen);
    for (int i = 1; i <= n; i++) {
        vector <int> p;
        for (int u = i; u != 0 && seen[u] == false; u = matchLef[u]) {
            seen[u] = true;
            p.push_back(u);
        }
        if (p.empty() == false) {
            c.push_back(p);
        }
    }
    return c;
}

int main() {
    freopen("strazi.in", "r", stdin);
    freopen("strazi.out", "w", stdout);
    
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].push_back(v);
    }
    
    matchMaximum();
    
    vector <vector <int>> c = findCover();
    
    printf("%d\n", (int)c.size() - 1);
    for (int i = 1; i < (int)c.size(); i++) {
        printf("%d %d\n", c[i - 1].back(), c[i].back());
    }
    for (int i = 0; i < (int)c.size(); i++) {
        for (const int u: c[i]) {
            printf("%d ", u);
        }
    }
    printf("\n");
    
    return 0;
}