// UUID: 5c77a354-fc30-454e-b07c-88bfeb1bbcb7
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> gr, grg;

int main() {
	int n, k;
	cin >> n >> k;
	gr.resize(n + 1);
	grg.resize(n + 1, vector<int>(n + 1));
	vector<int> befok(n + 1);
	befok[0] = 3;
	for (int i = 1; i <= k; i++) {
		int a, b;
		cin >> a >> b;
		gr[a].push_back(b);
		grg[a][b] = 1;
		befok[b]++;
	}
	queue<int> q;
	vector<int> ans;
	for (int i = 1; i <= n; i++) {
		if (!befok[i]) {
			q.push(i);
			ans.push_back(i);
		}
	}
	while (!q.empty()) {
		int a = q.front();
		q.pop();
		for (int i : gr[a]) {
			if (befok[i] == 1) {
				q.push(i);
				ans.push_back(i);
			}
			befok[i]--;
		}
	}
	if (ans.size() == n) {
		int x = -1;
		for (int i = 0; i < n - 1; i++) {
			if (!grg[ans[i]][ans[i + 1]]) {
				x = i;
			}
		}
		if (x != -1) {
			cout << "2\n";
			for (int i = 0; i < n; i++) {
				cout << ans[i] << ' ';
			}
			cout << '\n';
			for (int i = 0; i < n; i++) {
				if (i == x) {
					cout << ans[i + 1] << ' ';
				}
				else if (i == x + 1) {
					cout << ans[i - 1] << ' ';
				}
				else {
					cout << ans[i] << ' ';
				}
			}
		}
		else {
			cout << "1\n";
			for (int i = 0; i < n; i++) {
				cout << ans[i] << ' ';
			}
		}
	}
	else {
		cout << 0;
	}
}