#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

ifstream cin("strazi.in");
ofstream cout("strazi.out");

const int MAXN = 1000;

int n;
vector<int> g[MAXN];
int answer = 0, Left[MAXN], Right[MAXN], length[MAXN], a[MAXN][MAXN];
bool seen[MAXN];

bool Match(int node) {
    if (seen[node])
        return false;
    for (auto &nextNode : g[node])
        if (!Right[nextNode]) {
            Left[node] = nextNode;
            Right[nextNode] = node;
            return true;
        }
    seen[node] = true;
    for (auto &nextNode : g[node])
        if (Match(Right[nextNode])) {
            Left[node] = nextNode;
            Right[nextNode] = node;
            seen[node] = false;
            return true;
        }
    return false;
}

void Chain(int node) {
    answer++;
    while (Left[node]) {
        length[answer]++;
        a[answer][length[answer]] = node;
        node = Left[node] - n;
    }
    length[answer]++;
    a[answer][length[answer]] = node;
}

void MaximumMatching() {
    bool stop = false;
    while (!stop) {
        stop = true;
        memset(seen, false, sizeof(seen));
        for (int i = 1; i <= n; i++)
            if (!Left[i] && Match(i))
                stop = false;
    }
    for (int i = 1; i <= n; i++)
        if (!Right[i + n])
            Chain(i);
}

int main() {
    int m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b + n);
    }
    MaximumMatching();
    cout << answer - 1 << "\n";
    for (int i = 1; i < answer; i++)
        cout << a[i][length[i]] << " " << a[i + 1][1] << "\n";
    for (int i = 1; i <= answer; i++)
        for (int j = 1; j <= length[i]; j++)
            cout << a[i][j] << " ";
    return 0;
}