#include <fstream>
#include <vector>
#define MAXN 260
using namespace std;
ifstream f("strazi.in");
ofstream g("strazi.out");

int n,m,a,b,l[MAXN],r[MAXN],cuplmax;
vector<int> G[MAXN],traseu;
bool gata,uz[MAXN];

bool pair_up(int p);

int main()
{
    int i;
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>a>>b;
        G[a].push_back(b);}
    while(!gata){
        gata=1;
        for(i=1;i<=n;i++)
            uz[i]=0;
        for(i=1;i<=n;i++)
            if(!l[i]&&pair_up(i)){
                cuplmax++;
                gata=0;}}
    g<<n-1-cuplmax<<'\n';
    a=0;
    for(i=1;i<=n;i++)
        if(!r[i]){
            if(a)
                g<<a<<' '<<i<<'\n';
            a=i;
            traseu.push_back(a);
            while(l[a]){
                a=l[a];
                traseu.push_back(a);}}
    for(i=0;i<traseu.size();i++)
        g<<traseu[i]<<' ';
    f.close();
    g.close();
    return 0;
}

bool pair_up(int p){
    int i;
    if(uz[p])
        return 0;
    uz[p]=1;
    for(i=0;i<G[p].size();i++)
        if(!r[G[p][i]]||pair_up(r[G[p][i]])){
            l[p]=G[p][i];
            r[G[p][i]]=p;
            return 1;}
    return 0;}