#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#define REP(i, a, b) for(int i = a; i <= b; ++i)
#define FOR(i, n) REP(i, 1, n)
#define REPD(i, a, b) for(int i = a; i >= b; --i)
#define FOREACH(i, t) for (typeof(t.begin()) i = t.begin(); i != t.end(); ++i)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define read(n) int (n); scanf("%d", &(n))
#define read2(n, m) int (n), (m); scanf("%d %d", &(n), &(m))
#define read3(n, m, k) int (n), (m), (k); scanf("%d %d %d", &(n), &(m), &(k))
#define ll long long
#define x first
#define y second
#define mp make_pair
#define pb push_back

using namespace std;

int L[300], R[300], path[300];
bool U[300];
vector <int> G[300];
bool is[300][300];

bool pairup(int nod) {
    if (U[nod])
        return false;
    U[nod] = true;
    vector <int> :: iterator it;
    for (it = G[nod].begin(); it != G[nod].end(); ++it)
        if (R[*it] == 0 || pairup(R[*it])) {
            L[nod] = *it; R[*it] = nod;
            return true;
        }
    return false;
}

void dfs(int nod) {
    path[++path[0]] = nod;
    U[nod] = true;
    if (L[nod])
        dfs(L[nod]);
}

int main() {
    freopen("strazi.in", "r", stdin);
    freopen("strazi.out", "w", stdout);

    read2(N, M);
    FOR(i, M) {
        read2(xx, yy);
        G[xx].pb(yy);
        is[xx][yy] = true;
    }

    int match = 0;
    while (1) {
        bool nextMatch = false;
        memset(U, 0, sizeof(U));
        FOR(i, N)
            if (L[i] == 0 && pairup(i)) {
                ++match;
                nextMatch = true;
            }
        if (!nextMatch)
            break;
    }

    printf("%d\n", N - match - 1);
    memset(U, 0, sizeof(U));
    FOR(i, N)
        if (!U[i])
            dfs(i);
    FOR(i, N - 1)
        if (is[path[i]][path[i + 1]] == false)
            printf("%d %d\n", path[i], path[i + 1]);
    FOR(i, N)
        printf("%d ", path[i]);
    return 0;
}