#include <fstream>
#include <vector>

using namespace std;

#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)

const int MAX_N = 300;

ifstream fin ("strazi.in");
ofstream fout ("strazi.out");

int N, M, K, C[MAX_N], R[MAX_N];
vector <int> G[MAX_N], D[MAX_N];
char viz[MAX_N];

void citire()
{
	fin >> N >> M;

	for(int i = 1; i <= M; ++i)
	{
		int a, b;
		fin >> a >> b;

		G[a].push_back(b);
	}
}

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

	foreach(G[nod])
		if(!R[*it])
		{
			R[*it] = nod;
			C[nod] = *it;
			return 1;
		}

	foreach(G[nod])
		if(pairup(R[*it]))
		{
			R[*it] = nod;
			C[nod] = *it;
			return 1;
		}

	return 0;
}

void solve()
{
	for(bool ok = 1; ok; )
	{
		ok = 0;
		memset(viz, 0, sizeof viz);
		for(int i = 1; i <= N; ++i)
			if(C[i] == 0)
				ok |= pairup(i);
	}

	for(int i = 1; i <= N; ++i)
	{
		if(R[i]) continue;
		++K;

		for(int j = i; j; j = C[j])
			D[K].push_back(j);
	}

	fout << K-1 << "\n";

	for(int i = 1; i < K; ++i)
		fout << D[i].back() << " " <<  D[i+1].front() << "\n";

	for(int i = 1; i <= K; ++i)
		foreach(D[i])
			fout << *it << " ";

}

int main()
{
	citire();
	solve();
}