#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() {
    bool Check = 1;
    while (Check) {
        Check = 0;
        for (int i=1; i<=N; ++i)
            Seen[i] = 0;
        for (int i=1; i<=N; ++i)
            if (!RPair[i])
                Check |= PairUp(i);
    }
}

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

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

void Rezolvare() {
    ComputeGraphCoverage();

    for (int i=1; i<=N; ++i)
        Seen[i] = 0;

    Ans.push_back(0);
    for (int i=1, p; i<=N; ++i)
        if (!LPair[i]) {
            Seen[i] = 1;

            ConnectPoints.push_back(Ans[Ans.size()-1]);
            ConnectPoints.push_back(i);
            Ans.push_back(i);

            p = i;
            while (RPair[p]) {
                Ans.push_back(RPair[p]);
                p = RPair[p];
                Seen[p] = 1;
            }
        }

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

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

    return 0;
}