// UUID: 4bd7c332-9256-4c94-ad9c-48935e60e7e0
#include <bits/stdc++.h>
using namespace std;


int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> g(n + 1);
	vector<int> befok(n + 1);
	for (int i = 0; i < m; i ++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		befok[b] ++;
	}
	vector<int> ans;
	queue<int> q;
	for (int i = 1; i <= n; i ++) {
		if (befok[i] == 0) {
			q.push(i);
		}
	}
	while (!q.empty()) {
		int u = q.front();
		ans.push_back(u);
		q.pop();
		for (int v : g[u]) {
			befok[v] --;
			if (befok[v] == 0) q.push(v);
		}
	}
	if (ans.size() < n) {
		cout << 0;
		return 0;
	}
	auto ans2 = ans;
	bool done = false;
	for (int i = 1; i < n; i ++) {
		int u = ans[i - 1], v = ans[i];
		bool el = false;
		for (int c : g[u]) {
			if (c == v) {
				el = true;
				break;
			}
 		}
		if (!el) {
			swap(ans2[i - 1], ans2[i]);
			done = true;
			break;
		}
	}
	if (done) cout << 2 << "\n";
	else cout << 1 << "\n";
	for (int c : ans) cout << c << " ";
	cout << "\n";
	if (done) {
		for (int c : ans2) cout << c << " ";
	}
	return 0;
}