// UUID: 0c4c0248-212b-47fc-b167-407a3898e804
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,k; cin >> n >> k;
	vector<vector<int>> vec(n);
	vector<int> beel(n);
	for(int i=0; i<k; i++)
	{
		int a,b; cin >> a >> b;a--;b--;
		vec[a].push_back(b);
		beel[b]++;
	}
	queue<int> q;
	for(int i=0; i<n; i++)
		if(beel[i]==0)
			q.push(i);
	vector<int> ki;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		ki.push_back(x);
		for(auto& z:vec[x])
		{
			beel[z]--;
			if(beel[z]==0)
				q.push(z);
		}
	}
	for(auto& z:beel)
	{
		if(z!=0)
		{
			cout << 0;
			return 0;
		}
	}
	for(int i=0; i<ki.size()-1; i++)
	{
		bool b=true;
		for(auto& z:vec[ki[i]])
		{
			if(z==ki[i+1])
			{
				b=false;
				break;
			}
		}
		if(b)
		{
			cout << "2\n";
			for(int j=0; j<ki.size(); j++)
				cout << ki[j]+1 << " ";
			cout << "\n";
			for(int j=0; j<ki.size(); j++)
			{
				if(j==i)
				{
					cout << ki[j+1]+1 << " " << ki[j]+1 << " ";
					j++;
				}
				else
					cout << ki[j]+1 << " ";
			}
			return 0;
		}
	}
	cout << "1\n";
	for(auto& z:ki)
		cout << z+1 << " ";
}