// UUID: 6c72c73a-c072-45ac-9d18-f82e79b02635
#include <bits/stdc++.h>
using namespace std;

vector<int> c;
vector<int> t;
bool z = true;

void topo(int i, vector<vector<int>> &a) {
	c[i] = 1;
	for (auto j : a[i]) {
		if (c[j] == 1) z = false;
		if (!c[j]) topo(j, a);
	}
	c[i] = 2;
	t.push_back(i);
}

int main() {
	int n, k; cin >> n >> k;
    vector<vector<int>> a (n+1);
	for (int i = 0; i < k; i++) {
		int x, y; cin >> x >> y;
		a[x].push_back(y);
	}
	c.resize(n+1);
	for (int i = 1; i <= n; i++) {
		if (!c[i]) {
			topo(i, a);
		}
		if (!z) {
			cout << 0 << endl;
			return 0;
		}
	}
	z = false;
	int w = 0;
	for (int i = n-1; i > 0; i--) {
		int f = t[i];
		int m = t[i-1];
		bool d = false;
		for (auto j : a[f]) {
			if (j == m) d = true;
		}
		if (!d) {
			z = true;
			w = i;
		}
	}
	if (!z) {
		cout << 1 << endl;
		for (int i = n-1; i >= 0; i--) {
			cout << t[i] << " ";
		}
	}
	else {
		cout << 2 << endl;
		for (int i = n-1; i >= 0; i--) {
			cout << t[i] << " ";
		}
		cout << endl;
		swap(t[w], t[w-1]);
		for (int i = n-1; i >= 0; i--) {
			cout << t[i] << " ";
		}
	}
}