#include <bits/stdc++.h>

#define MAXN 260

int N, M;
std::vector <int> ADC[MAXN];

inline void AddEdge(int x, int y) {
    ADC[x].push_back(y);
}

std::ifstream In("strazi.in");
std::ofstream Out("strazi.out");

int RPair[MAXN],
    LPair[MAXN];

bool Seen[MAXN];
bool PairUp(int x) {
    if (Seen[x]) return false;
    Seen[x] = 1;

    for (auto vecin:ADC[x]) {
        if (!LPair[vecin] || PairUp(LPair[vecin])) {
            LPair[vecin] = x;
            RPair[x] = vecin;
            return true;
        }   return false;
    }
}

void ComputeGraphCoverage() {
    for (int i=1, j; i<=N; ++i) {
        PairUp(i);
        for (j=1; j<=N; ++j)
            Seen[j] = 0;
    }
}

std::vector <int> Ans;
std::vector <int> ConnectPoints;

void Walk(int x) {
    if (Seen[x]) return;
    Seen[x] = 1;

    Ans.push_back(x);

    if (!RPair[x]) return;
    Walk(RPair[x]);
}

void Citire() {
    In >> N >> M;
    for (int i=0, x, y; i<M; ++i)
        In >> x >> y,
        AddEdge(x, y);
}

void Rezolvare() {
    ComputeGraphCoverage();

    int NWalks = 0;
    for (int i=1; i<=N; ++i)
        if (!Seen[i])
            ++NWalks, Walk(i),
            ConnectPoints.push_back(Ans[Ans.size()-1]);

    Out << NWalks-1 << '\n';
    for (int i=0; i<NWalks-1; ++i)
        Out << ConnectPoints[i] << ' ' << ConnectPoints[i+1] << '\n';
    for (int i=0; i<Ans.size(); ++i)
        Out << Ans[i] << ' ';
    Out << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}