#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;

const int NMAX = 260;

vector <int> graph[NMAX];
bool adj[NMAX][NMAX], vis[NMAX];
int path[NMAX], left[NMAX], right[NMAX];

bool pairUp (int node) {
    if(vis[node])
        return 0;
    vis[node] = 1;

    for(vector <int>::iterator it = graph[node].begin(); it != graph[node].end(); ++ it)
        if(!left[*it] || pairUp(left[*it])) {
            right[node] = *it;
            left[*it] = node;

            return 1;
        }
    return 0;
}

void dfs (int node) {
    path[++ path[0]] = node;
    if(right[node])
        dfs(right[node]);
}

int main() {
    freopen("strazi.in", "r", stdin);
    freopen("strazi.out", "w", stdout);
    int flag, n, m, i, x, y, cnt;

    scanf("%d%d", &n, &m);
    for(i = 1; i <= m; ++ i) {
        scanf("%d%d", &x, &y);
        graph[x].push_back(y);
        adj[x][y] = 1;
    }

    flag = 1;
    cnt = 0;
    while(flag) {
        memset(vis, 0, sizeof(vis));
        flag = 0;
        for(i = 1; i <= n; ++ i)
            if(!right[i] && pairUp(i)) {
                ++ cnt;
                flag = 1;
            }
    }

    printf("%d\n", n - cnt - 1);
    for(i = 1; i <= n; ++ i)
        if(!left[i])
            dfs(i);

    for(i = 1; i < path[0]; ++ i)
        if(!adj[path[i]][path[i + 1]])
            printf("%d %d\n", path[i], path[i + 1]);
    for(i = 1; i <= n; ++ i)
        printf("%d ", path[i]);
    return 0;
}