// UUID: 9a884aed-f60d-4a0c-a6bc-75ea601c61da
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> graph;
vector<bool> been;
vector<int> solution;

void dfs(int node){
	been[node]=true;
	for(int next:graph[node]){
		if(!been[next]) dfs(next);
	}
	solution.push_back(node);
}


int main() {
	int N,K;
	cin >> N >> K;
	graph.resize(N+1);

	for(int i=0; i<K; i++){
		int a,b;
		cin >> a >> b;
		graph[a].push_back(b);
	}

	been.resize(N+1,false);

	for(int i=1; i<=N; i++){
		if(!been[i]) dfs(i);
	}

	been.assign(N+1,false);
	bool check;
	bool AtLeastTwo=false;
	int SwapIndex=-1;
	int i=0;
	reverse(solution.begin(),solution.end());
	
	for(int place:solution){
		check=false;
		been[place]=true;
		for(int u:graph[place]){
			if(been[u]) {cout << 0; return 0;}
			if(i < N && u == solution[i+1]) {check=true;}
		}
		if(!check && i<N-1){AtLeastTwo=true; SwapIndex=i;}
		i++;
	}
	if(AtLeastTwo) cout << "2\n";
	else cout << "1\n";
	
	for(int n:solution) cout << n << " ";
	if (AtLeastTwo) {
		cout << "\n";
		swap(solution[SwapIndex], solution[SwapIndex + 1]);
		for(int n:solution) cout << n << " ";
	}
return 0;
}