// UUID: c33e5532-d075-4369-bc1f-b50a0dc75a7e
#include <bits/stdc++.h>
using namespace std;

void melysegi(int i,vector<vector<int>> &matrix,vector<bool> &volt, vector<int> &sorrend, bool &ok) {
	for (int j = 0;j < matrix[i].size();j++) {
		if (!volt[matrix[i][j] - 1]) {
			volt[matrix[i][j] - 1] = true;
			melysegi(matrix[i][j] - 1,matrix,volt, sorrend, ok);
			sorrend.push_back(matrix[i][j]);
		}
		else {
			if (find(sorrend.begin(), sorrend.end(), matrix[i][j]) != sorrend.end()) {
			}
			else {
				cout << 0;
				ok = false;
			}
		}
	}
}
int main() {
	bool ok;ok = true;
	int n, k; cin >> n >> k;
	int temp,temp2;temp = 0,temp2 = 0;
	vector<vector<int>> matrix(n,vector<int>(0,0));
	for (int i = 0;i < k;i++) {
		cin >> temp >> temp2;
		matrix[temp - 1].push_back(temp2);
	}
	vector<int> sorrend(0,0);
	vector<bool> volt(n,false);
	for (int i = 0;i < n;i++) {
		if (volt[i] == false) {
			volt[i] = true;
			melysegi(i, matrix, volt, sorrend, ok);
			sorrend.push_back(i + 1);
		}
	}
	for (int i = 0;i < n - 1;i++) {
		if (!(find(matrix[sorrend[i + 1] - 1].begin(), matrix[sorrend[i + 1] - 1].end(), sorrend[i]) != matrix[sorrend[i + 1] - 1].end())) {
			cout << 2 << endl;
			for (int j = 0;j < n;j++) { 
				cout << sorrend[n - j - 1] << " ";
			}
			temp = sorrend[i + 1];
			sorrend[i + 1] = sorrend[i];
			sorrend[i] = temp;
			ok = false;
			cout << endl;
			break;
		}
	}
	if (ok) {
		cout << 1 << endl;
	}
	for (int i = 0;i < n;i++) {
		cout << sorrend[n - i - 1] << " ";
	}
}