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

#define DIM 256

using namespace std;

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

int n, m, k;

vector<int> l[DIM];

int L[DIM], R[DIM];

bool vis[DIM];

int path[DIM];

bool mat[DIM][DIM];

bool cupleaza(int nod) {
	
	vis[nod] = true;
	
	for (int i = 0; i < l[nod].size(); i++) {
	
		if (!R[l[nod][i]]){
			
			L[nod] = l[nod][i];
			R[l[nod][i]] = nod;
			
			return true;
		
		}

	}
	
	for (int i = 0; i < l[nod].size(); i++) {
		
		if (!vis[R[l[nod][i]]] && cupleaza(R[l[nod][i]])){
			
			L[nod] = l[nod][i];
			R[l[nod][i]] = nod;
		
			return true;
		
		}

	}
	
	return false;

}

void DFS(int node) {

	path[++k] = node;

	if (L[node])
		DFS(L[node]);

}

int main() {

	fin >> n >> m;

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

		int x, y;

		fin >> x >> y;

		mat[x][y] = true;

		l[x].push_back(y);

	}

	bool ok;

	int cuplaj = 0;

	do {

		ok = false;

		memset(vis, false, sizeof vis);

		for (int i = 1; i <= n; i++){
	
			if (!L[i] && cupleaza(i)) {
				
				cuplaj++;
				ok = 1;
			
			}

		}
	
	} while (ok);

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

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

		if (!R[i])
			DFS(i);

	}

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

		if (!mat[path[i]][path[i + 1]])
			fout << path[i] << " " << path[i + 1] << "\n";

	}

	for (int i = 1; i <= k; i++)
		fout << path[i] << " ";

	return 0;

}