#include<fstream>
#include<vector>
using namespace std;
int n,m,st[260],dr[260],nrd,start[260],sfarsit[260];
vector <int> G[260],v;
bool viz[260];

inline bool Hopcroft_Karp(int nod)
{
    if(viz[nod]==true)
        return false;
    viz[nod]=true;
     
    vector <int>::iterator it;
    for(it=G[nod].begin();it!=G[nod].end();it++)
    {
        if(!st[*it])
        {
            st[*it]=nod;
            dr[nod]=*it;
            return true;
        }
    }
    for(it=G[nod].begin();it!=G[nod].end();it++)
    {
        if(Hopcroft_Karp(st[*it])==true)
        {
            st[*it]=nod;
            dr[nod]=*it;
            return true;
        }
    }
    return false;
}

int main()
{
	int i,x,y;
	bool modificare=true;
	ifstream fin("strazi.in");
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		G[x].push_back(y);
	}
	fin.close();
    
    while(modificare)
    {
        modificare=false;
        for(i=1;i<=n;i++)
        {
            if(!dr[i])
            {
                if(Hopcroft_Karp(i)==true)
                    modificare=true;
            }
        }
        for(i=1;i<=n;i++)
            viz[i]=false;
    }
	for(i=1;i<=n;i++)
	{
		if(!dr[i])
		{
			nrd++;
			v.push_back(i);
		}
	}
	for(i=0;i<nrd;i++)
	{
		sfarsit[i]=v[i];
		x=v[i];
		while(st[x])
			x=st[x];
		start[i]=x;
	}
	nrd--;
	
	ofstream fout("strazi.out");
	fout<<nrd<<"\n";
	for(i=0;i<nrd;i++)
	{
		fout<<sfarsit[i]<<' '<<start[i+1]<<"\n";
		dr[sfarsit[i]]=start[i+1];
	}
	x=start[0];
	while(x && !viz[x])
	{
		viz[x]=true;
		fout<<x<<' ';
		x=dr[x];
	}
	fout<<"\n";
	fout.close();
	return 0;
}