/*   Find the number of directed paths then add nr_path - 1 edges*/


#include <bits/stdc++.h>
#define maxN 260
#define pii pair <int, int>
#define mp make_pair
FILE *fin  = freopen("strazi.in", "r", stdin);
FILE *fout = freopen("strazi.out", "w", stdout);

using namespace std;
int N, M;
vector <int> G[2*maxN];
int Pair[2 * maxN];
bitset <2*maxN> used;
vector <int> path;
vector <pii> edge;


void read(){
    scanf("%d %d", &N, &M);
    for(int i = 1; i <= M; ++ i){
        int x, y;
        scanf("%d %d", &x, &y);
        G[x].push_back(y + N);
    }
}

bool PairUp(int node){
    if(used.test(node)) return 0;
    used.set(node);
    for(int son : G[node])
        if(Pair[son] == -1 || PairUp(Pair[son])){
            Pair[node] = son;
            Pair[son] = node;
            return 1;
        }
    return 0;
}

void Match(){
    memset(Pair, -1, sizeof(Pair));
    bool change;
    do{
        change = false;
        used.reset();
        for(int i = 1; i <= N; ++ i)
            if(Pair[i] == -1)
                change |= PairUp(i);
    } while(change);
}

int Path(int node){
    used.set(node);
    path.push_back(node);
    if(Pair[node] == -1)
        return node;
    node = Pair[node] - N; // right
    //path.push_back(node);
    return Path(node);
}

void write(){
    int lst = 0;
    used.reset();
    for(int i = 1; i <= N; ++ i)
        if(Pair[i + N] == -1 && !used.test(i)){
            if(lst)
               edge.push_back(mp(lst, i));
            lst = Path(i);
            if(lst > N) lst -= N;
        }
    printf("%d\n", edge.size());
    for(pii e : edge)
        printf("%d %d\n", e.first, e.second);
    for(int node : path)
        printf("%d ", node);
}

int main(){
    read();
    Match();
    write();
    return 0;
}