#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>

#define DIM 260
#define infile "strazi.in"
#define outfile "strazi.out"

std::ifstream fin(infile);
std::ofstream fout(outfile);

std::vector<int> graph[DIM], path;

bool edges[DIM][DIM], vis[DIM];

int left[DIM], right[DIM];


bool findPair(int node) {

	if (vis[node]) {

		return false;

	}

	vis[node] = true;

	for (int adjacentNode : graph[node]) {

		if (!right[adjacentNode]) {

			left[node] = adjacentNode;

			right[adjacentNode] = node;

			return true;

		}

	}

	for (int adjacentNode : graph[node]) {

		if (findPair(right[adjacentNode])) {

			left[node] = adjacentNode;

			right[adjacentNode] = node;

			return true;

		}

	}

	return false;

}


void findPath(int node) {

	path.push_back(node);

	if (left[node]) {

		findPath(left[node]);
		
	}

}


int main() {

	int n, m;

	fin >> n >> m;

	for (int i = 1; i <= m; ++i) {

		int x, y;

		fin >> x >> y;

		graph[x].push_back(y);

		edges[x][y] = true;

	}


	bool ok;
	int mapCount = 0;

	do {

		ok = false;

		memset(vis, false, sizeof vis);

		for (int i = 1; i <= n; ++i) {

			if (!left[i] && findPair(i)) {

				++mapCount;

				ok = true;

			}

		}

	} while (ok);


	//find minimum number of necessary edges
	int newEdgesCount = n - 1 - mapCount;

	fout << newEdgesCount << '\n';


	//find final path
	for (int i = 1; i <= n; ++i) {

		if (!right[i]) {

			findPath(i);

		}

	}


	//writes new edges
	for (int i = 0; i < path.size() - 1; ++i) {

		if (edges[path[i]][path[i + 1]]) {

			continue;

		}

		fout << path[i] << ' ' << path[i + 1] << '\n';

	}


	//writes path
	for (int i = 0; i < path.size(); ++i) {

		fout << path[i] << ' ';

	}

	return 0;

}

//Trust me, I'm the Doctor!