#include<fstream>
#include<vector>
#include<bitset>
#define f first
#define s second
using namespace std;
int n, m, i, x, y, nr, ok, u, p, nod;
int d[260], a[260], b[260], c[260];
vector<int> v[260];
bitset<260> viz;
pair<int, int> sol[260];
ifstream fin("strazi.in");
ofstream fout("strazi.out");
int cuplaj(int nod){
    if(viz[nod] == 1){
        return 0;
    }
    viz[nod] = 1;
    int i, vecin;
    for(i = 0; i < v[nod].size(); i++){
        vecin = v[nod][i];
        if(b[vecin] == 0){
            a[nod] = vecin;
            b[vecin] = nod;
            return 1;
        }
    }
    for(i = 0; i < v[nod].size(); i++){
        vecin = v[nod][i];
        if(cuplaj(b[vecin])){
            a[nod] = vecin;
            b[vecin] = nod;
            return 1;
        }
    }
    return 0;
}
int main(){
    fin>> n >> m;
    for(i = 1; i <= m; i++){
        fin>> x >> y;
        v[x].push_back(y + n);
    }
    do{
        ok = 0;
        viz.reset();
        for(i = 1; i <= n; i++){
            if(a[i] == 0 && cuplaj(i)){
                ok = 1;
            }
        }
    }while(ok == 1);
    for(i = 1; i <= n; i++){
        if(b[i + n] == 0){
            c[++u] = i;
        }
    }
    nod = c[1];
    p = 2;
    for(i = 1; i <= n; i++){
        d[i] = nod;
        if(a[nod] != 0){
            nod = a[nod] - n;
            continue;
        }
        if(p <= u){
            nr++;
            sol[nr] = make_pair(nod, c[p]);
            nod = c[p];
            p++;
        }
    }
    fout<< nr <<"\n";
    for(i = 1; i <= nr; i++){
        fout<< sol[i].f <<" "<< sol[i].s <<"\n";
    }
    for(i = 1; i <= n; i++){
        fout<< d[i] <<" ";
    }
    return 0;
}