// UUID: 5cc0429d-2be2-418b-a8b4-8245c7a2b00d
#include <bits/stdc++.h>
using namespace std;

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

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


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.resize(N+1,false);
	bool check;
	bool AtLeastTwo=false;
	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 << u << place; return 0;}
			if(i < N && u == solution[i+1]) {check=true;cout << place << " "<< u << "\n";}
		}
		if(!check && i<N-1){AtLeastTwo=true;}
		i++;
	}
	if(AtLeastTwo) cout << "2\n";
	else cout << "1\n";
	
	for(int n:solution) cout << n << " ";
return 0;
}