// UUID: e4bf84e2-ff8d-4af5-898a-feb8cb174d1d
#include <bits/stdc++.h>
using namespace std;




int main() {
	int n, m;
	cin>>n>>m;
	vector<int> beel(n);
	vector<vector<int>> a(n);
	for(int i=0;i<m;i++){
		int x, y;cin>>x>>y;
		y--;x--;
		beel[y]++;
		a[x].push_back(y);
	}
	/*for(int i=0;i<n;i++){
		for(int x: a[i]){
			cout<<x<<' ';
		}
		cout<<'\n';
	}
	cout<<'\n';*/
	vector<int> topo;
	queue<int> q;
	int nn=0;
	for(int i=0;i<n;i++){
		if(beel[i]==0){	q.push(i);nn++;};
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		topo.push_back(x);
		for(int z: a[x]){
			beel[z]--;
			if(beel[z]==0){
				q.push(z);nn++;
			}
		}
	}
	/*for(int i=0;i<n;i++){
		cout<<topo[i]<<' ';
	}*/
	//cout<<'\n'<<'\n';
	if(nn!=n){
		cout<<0<<'\n';return 0;
	}
	int hi=-1, ha=-1;
	for(int i=0;i<n-1;i++){
		bool b=true;
		for(int x: a[topo[i]]){
			if(x==topo[i+1]){
				b=false;
				break;
			}
		}
		if(b){
			hi=i;ha=i+1;
		}
	}
	if(hi==-1){
		cout<<1<<'\n';
		for(int x: topo){
			cout<<x+1<<' ';
		}
	}else{
		//cout<<hi<<' '<<ha<<"\n\n";
		cout<<2<<'\n';
		for(int i=0;i<n;i++){
			if(i==hi){
				cout<<topo[i+1]+1<<' ';
			}	else if(i==ha){
				cout<<topo[i-1]+1<<' ';
			}else{
				cout<<topo[i]+1<<' ';
			}
		}
		cout<<'\n';
		for(int i=0;i<n;i++){
			cout<<topo[i]+1<<' ';
		}
		cout<<'\n';
	}
}