// UUID: 6e77ad08-6b44-46df-a987-863bb71fd2ac
#include <bits/stdc++.h>
#include <cctype>
using namespace std;

void melysegi(int i, vector<vector<int>> &mat, vector<bool> &volt, vector<int> &sor, bool &possible) {
	/*volt[v] = true;
	for(int edge : mat[v]){
		if(!volt[edge]){
			melysegi(edge, mat, volt, sor);
		}
		else if(edge != parent[v]){
				
		}
	}
	sor.push_back(edge);*/
	
	for (int j = 0;j < mat[i].size();j++) {
		if (!volt[mat[i][j]]) {
			volt[mat[i][j]] = true;
			melysegi(mat[i][j], mat, volt, sor, possible);
			sor.push_back(mat[i][j]);	
		}
		else {
			if(find(sor.begin(), sor.end(), mat[i][j]) != sor.end()) {
			}
			else {
				possible = false;
			}
		}
	}
	
}

int main() {
	bool possible = true;
	int n, m; cin >> n >> m;
	int a, b;
	vector<vector<int>> mat(n,vector<int>(0,0));
	for (int i = 0;i < m;i++) {
		cin >> a >> b;
		mat[a - 1].push_back(b - 1);
	}
	vector<int> sor(0,0);
	vector<bool> volt(n,false);
	for (int i = 0;i < n;i++) {
		if (!volt[i]) {
			volt[i] = true;
			melysegi(i, mat, volt, sor, possible);
			sor.push_back(i);
		}
	}
	reverse(sor.begin(),sor.end());
	vector<int> sor2(0,0);
	sor2 = sor;
	int temp = 0;
	if (possible) {
		for (int i = 0;i < n - 1;i++) {
			if(find(mat[sor[i]].begin(), mat[sor[i]].end(), sor[i + 1]) == sor.end() or mat[sor[i]].size() == 0) {
				cout << 2 << endl;
				temp = sor[i + 1];
				sor[i + 1] = sor[i];
				sor[i] = temp;
				for(int j:sor) {
					cout << j + 1 << " ";
				}
				cout << endl;
				break;
			}
			if (i == n - 2) {
				cout << 1 << endl;
			}
		}
		for(int i:sor2) {
			cout << i + 1 << " ";
		}
	}
	else {
		cout << 0;
	}
	cout << 0;
}