#include <cstdio>
#include <cstring>

#define fin  "strazi.in"
#define fout "strazi.out"

const int Nmax = 256;

int N,M,g[Nmax][Nmax];
int cnt;
int viz[Nmax],st[Nmax],dr[Nmax];

void readdata()
{
	int i,x,y;

	freopen(fin,"r",stdin);

	scanf("%d%d",&N,&M);

	for (i=1;i<=M;++i)
	{
		scanf("%d%d",&x,&y);
		g[x][y]=1;
	}
}

int cupleaza(int nod)
{
	int i;

	if ( viz[ nod ] )
		return 0;
	viz[nod]=1;

	for (i=1;i<=N;++i)
	{
		if ( !g[nod][i] )
			continue;
		if ( !dr[i] || cupleaza(i) )
		{
			dr[i] = nod;
			st[nod] = i;
			return 1;
		}
	}

	return 0;
}

int df(int nod)
{
	if ( st[nod] == 0 )
		return nod;
	return df(st[nod]);
}

void df2(int nod)
{
	if ( !nod )
		return ;
	printf(" %d",nod);
	df2(st[nod]);
}

void solve()
{
	int i,j,last;

	for (i=1;i<=N;++i)
	{
		memset(viz,0,sizeof(viz));
		cupleaza(i);
	}

	for (i=1;i<=N;++i)
		if (!st[i])
			++cnt;

	freopen(fout,"w",stdout);

	printf("%d\n",cnt-1);

	//adaug muchii
	for (i=1;i<=N;++i)
		if ( dr[i] == 0 )
		{
			last=df(i);
			for (j=1;j<=N;++j)
				if ( dr[j] == 0 && j!=i )
				{
					st[last] = j;
					dr[j] = last;
					printf("%d %d\n",last,j);
					break;
				}
		}

	for (i=1;i<=N;++i)
		if (dr[i]==0)
		{
			printf("%d",i);
			df2(st[i]);
			printf("\n");
			return ;
		}
}

int main()
{
	readdata();
	solve();
	return 0;
}