#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
#include <cstdio>
#include <cstring>
#include <cassert>

#define INFI 0x3f3f3f3f

using namespace std;

int N, M, a, b;
ifstream fin;
ofstream fout;

bool adj[256][256];
vector<int> ts, din, prev, sol;
vector<bool> seen, del;

void dfs(int u) {
	seen[u] = true;

	for (int i = 0; i < N; ++ i)
		if (adj[i][u] && !seen[i])
			dfs(i);

	ts.push_back(u);
}

void top_sort(void) {
	seen.resize(N, false);

	for (int i = 0; i < N; ++ i)
		if (!seen[i])
			dfs(i);
}

void remove_path(int u) {
	if (u == -1)
		return;

	assert(!del[u]);
	del[u] = true;

	remove_path(prev[u]);
	sol.push_back(u);
}

int go(void) {
	din.resize(N, 1);
	prev.resize(N, -1);

	if (sol.size() == N)
		return 0;

	for (int i = 0; i < N; ++ i) {
		if (del[i])
			din[i] = -INFI;
		else
			din[i] = 1;

		prev[i] = -1;
	}

	for (int i = 0; i < N; ++ i) {
		if (del[ts[i]])
			continue;

		for (int j = 0; j < i; ++ j) {
			if (del[ts[j]])
				continue;

			int u = ts[j];
			int v = ts[i];

			if (adj[u][v] && din[v] < din[u] + 1) {
				//cerr << u << " " << v << endl;
				din[v] = din[u] + 1;
				prev[v] = u;
			}
		}
	}

	/*
	copy(din.begin(), din.end(), ostream_iterator<int>(cerr, " "));
	cerr << endl;
	copy(prev.begin(), prev.end(), ostream_iterator<int>(cerr, " "));
	cerr << endl;
	*/

	int best = -1;
	int bp = -1;

	for (int i = 0; i < N; ++ i)
		if (best < din[i]) {
			best = din[i]; bp = i;
		}

	if (best == -1)
		return 0;

	assert(!del[bp]);

	remove_path(bp);
	return best;
}

int main(void) {
	fin.open("strazi.in");
	fout.open("strazi.out");

	memset(adj, 0x0, sizeof(adj));

	fin >> N >> M;

	for (int i = 0; i < M; ++ i) {
		fin >> a >> b;
		adj[a - 1][b - 1] = true;
	}

	del.resize(N, false);
	top_sort();

	while (true) {
		if (go() == 0)
			break;
	}

	int ret = 0;

	for (int i = 0; i < N - 1; ++ i)
		if (!adj[sol[i]][sol[i + 1]])
			++ ret;

	fout << ret << endl;

	for (int i = 0; i < N - 1; ++ i)
		if (!adj[sol[i]][sol[i + 1]])
			fout << sol[i] + 1 << " " << sol[i + 1] + 1 << endl;

	for (int i = 0; i < N; ++ i) {
		fout << sol[i] + 1;

		if (i == N - 1)
			fout << endl;
		else
			fout << " ";
	}

	return 0;
}