#include <fstream>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

int maxflux(const int surs, const int dest, const vector<vector<int>>& vec,
		const vector<vector<int>>& cap, vector<vector<int>>& flux){

	const int n = vec.size();
	vector<int> tata(n, -1);
	queue<int> de_viz;
	int rez = 0;
	while(true){
		de_viz.push(surs);
		while(!de_viz.empty()){
			const int cur = de_viz.front();
			de_viz.pop();
			for(const auto next : vec[cur]){
				if(tata[next] == -1 && flux[cur][next] < cap[cur][next]){
					tata[next] = cur;
					if(next != dest){
						de_viz.push(next); } } } }
		if(tata[dest] == -1){
			return rez; }
		for(const auto frunza : vec[dest]){
			if(cap[frunza][dest] <= flux[frunza][dest] || tata[frunza] == -1){
				continue; }
			int f_min = 1000000;
			tata[dest] = frunza;
			for(int i = dest; i != surs; i = tata[i]){
				f_min = min(f_min, cap[tata[i]][i] - flux[tata[i]][i]); }
			rez += f_min;
			for(int i = dest; i != surs; i = tata[i]){
				flux[tata[i]][i] += f_min;
				flux[i][tata[i]] -= f_min; } }
		fill(begin(tata), end(tata), -1); } }

int main(){
	ifstream f("strazi.in");
	ofstream g("strazi.out");

	int n, m;
	f >> n >> m;
	vector<vector<int>> vec(2*n+2), cap(2*n+2, vector<int>(2*n+2, 0)), flux(2*n+2, vector<int>(2*n+2, 0));

	auto add_muc = [&](const int a, const int b){
		vec[a].push_back(b);
		vec[b].push_back(a);

		cap[a][b] = 1; };

	for(int i = 1; i <= n; ++i){
		add_muc(0, i);
		add_muc(n+i, 2*n+1); }
	for(int i = 0, a, b; i < m; ++i){
		f >> a >> b;
		add_muc(a, n+b); }

	maxflux(0, 2*n+1, vec, cap, flux);
	auto follows = [&](const int x){
		for(int i = 1; i <= n; ++i){
			if(flux[x][i+n]){
				return i; } } };
	
	vector<vector<int>> trasee;
	vector<bool> luat(n+1, false);
	for(int i = 1; i <= n; ++i){
		if(!luat[i] && flux[i+n][2*n+1] == 0){
			trasee.emplace_back(1, i);
			luat[i] = true;
			for(int j = i; flux[0][j] != 0; ){
				j = follows(j);
				luat[j] = true;
				trasee.back().push_back(j); } } }

	g << (trasee.size()-1) << '\n';
	for(int i = 0; i < trasee.size()-1; ++i){
		g << trasee[i].back() << ' ' << trasee[i+1].front() << '\n'; }
	for(const auto& x : trasee){
		for(const auto y : x){
			g << y << ' '; } }
	return 0; }