// UUID: bca1ac27-551e-4a0f-ba8f-7e6c77b04626
#include <bits/stdc++.h>
using namespace std;

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

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

int main() {
	int n, k;
	cin >> n >> k;
	graf.resize(n+1);
	be.resize(n+1);
	ki.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(be[i] == false){
			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] << " ";
			}
		}
	}
}