#include <vector>
#include <fstream>
#include <cstring>
#include <cstdio>
#include <utility>

using namespace std;

ifstream f_in("strazi.in");
ofstream f_out("strazi.out");

const int MAX_N = 260;

vector<int> G[MAX_N];

int n,m;

int mate[MAX_N];
int taken_by[MAX_N];
bool init[MAX_N];

bool viz[MAX_N];

bool pair_up(const int nod)
{
    if(viz[nod])
        return false;
    viz[nod] = 1;
    for(auto it:G[nod]){
        if(!taken_by[it]){
            mate[nod] = it;
            taken_by[it] = nod;
            return true;
        }
    }
    for(auto it:G[nod]){
        if(pair_up(taken_by[it])){
            mate[nod] = it;
            taken_by[it] = nod;
            return true;
        }
    }
    return false;
}

void road(const int nod)
{
    if(viz[nod])
        return;
    viz[nod] = 1;
    f_out << nod << " ";
    printf("%d ",nod);
    return road(mate[nod]);
}
vector<pair<int,int> > extra;

void match()
{
    int i;
    bool matched = true;
    while(matched){
        matched = false;
        for(i = 1 ; i <= n ; ++ i)
            if(!viz[i] && !mate[i])
                matched |= pair_up(i);
        memset(viz,0,sizeof(viz));
    }
}

int main()
{
    f_in >> n >> m;
    int i,j,a,b;
    int start;
    for(i = 1 ; i <= m ; ++ i){
        f_in >> a >> b;
        G[a].push_back(b);
        start = a;
        init[a] = true;
    }
    match();
    for(i = 1 ; i <= n ; ++ i)for(j = 1 ; j <= n ; ++ j){
        if(i == j)continue;
        G[i].push_back(j);
    }
    match();

    for(i = 1 ; i <= n ; ++ i){
        if(!init[i] && mate[i] != start)
            extra.push_back(make_pair(i,mate[i]));
    }

    f_out << extra.size() << "\n";
    printf("%d\n",extra.size());
    for(auto it : extra){
        f_out << it.first << " " << it.second << "\n";
        printf("%d %d\n",it.first,it.second);
    }

    road(start);
    return 0;
}