// UUID: bb1a4162-c6cf-4810-a3c9-1650d193ef13
#include <bits/stdc++.h>
using namespace std;

bool nemLehet = false;
vector<vector<int>> graf;
vector<int> be;
vector<int> ki;
vector<int> topol;

void bejar(int csucs){
	be.push_back(csucs);
	for(int i = 0; i < graf[csucs].size(); i++){
		if(count(be.begin(), be.end(), graf[csucs][i]) == 0 && count(ki.begin(), ki.end(), graf[csucs][i]) == 0){
			bejar(graf[csucs][i]);
		}
		else if(count(be.begin(), be.end(), graf[csucs][i]) == 1 && count(ki.begin(), ki.end(), graf[csucs][i]) == 0){
			nemLehet = true;
		}
	}
	ki.push_back(csucs);
	topol.push_back(csucs);
}

int main() {
	int n, k;
	cin >> n >> k;
	graf.resize(n+1);
	for(int i = 0; i < k; i++){
		int a, b;
		cin >> a >> b;
		graf[a].push_back(b);
	}
	for(int i = 1; i <= n; i++){
		if(count(be.begin(), be.end(), i) == 0){
			bejar(i);
		}
	}
	if(nemLehet){
		cout << 0;
		return 0;
	}
	reverse(topol.begin(), topol.end());
	int csere = -1;
	for(int i = 0; i < n-1; i++){
		if(count(graf[topol[i]].begin(), graf[topol[i]].end(), topol[i+1]) == 0){
			csere = i;
		}
	}
	if(csere == -1){
		cout << 1 << endl;
		for(int i = 0; i < n; i++){
			cout << topol[i] << " ";
		}
	}
	else{
		cout << 2 << endl;
		for(int i = 0; i < n; i++){
			cout << topol[i] << " ";
		}
		cout << endl;
		for(int i = 0; i < n; i++){
			if(i == csere){
				cout << topol[i+1] << " " << topol[i] << " ";
			}
			else if(i != csere+1){
				cout << topol[i] << " ";
			}
		}
	}
}