#include <bits/stdc++.h>
using namespace std;
vector<int> g[2000001];
int main() {
	int n, m;
	cin>>n>>m;
	vector<int> c;
	c.assign(n+1, 0);
	for (int i=0; i<m;i++){
		int x,y;
		cin>>x>>y;
		c[y]++; 
		g[x].push_back(y);
	}
	queue<int> q;
	for (int i=1;i<=n;i++){
		if (c[i]==0) q.push(i);
	}
	int cnt=0; 
	vector<int> ans;
	pair<int, int> ans2;
	bool van=false, volte=false; 
	while (!q.empty()){
		cnt++;
		if (q.size()>1 && !volte){
			ans2.first=q.front();
			van=true; 
			volte=true;
		}
		int v=q.front();
		ans.push_back(v);
		q.pop();
		if (van){
			ans2.second=q.front(); 
			van=false; 
		}
		for (int edge:g[v]){
			c[edge]-=1;
			if (c[edge]==0) q.push(edge);
		} 
	}
	if (cnt!=n){
		cout<<0<<endl;
		return 0; 
	}
	if (!volte){
		cout<<1<<endl;
		for (int i:ans) cout<<i<<" "; 
	}
	else{
		cout<<2<<endl;
		vector<int> mego; 
		for (int i=0; i<n;i++){
			cout<<ans[i]<<" ";
			if (ans[i]==ans2.first) mego.push_back(ans2.second);
			else{
				if (ans[i]==ans2.second) mego.push_back(ans2.first);
				else mego.push_back(ans[i]);
			}
		}
		cout<<endl;
		for (int i:mego) cout<<i<<" ";
	}
	
}