// UUID: 4e4cb332-b7cf-48bd-be71-229167dba423
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pll=pair<ll, ll>;

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	ll n, k; cin >> n >> k;
	vector<vector<ll>> vec(n);
	vector<ll> count(n);
	queue<ll> q;
	vector<ll> out;
	for (ll i=0; i<k; i++){
		ll a, b; cin >> a >> b; a--; b--;
		vec[a].push_back(b);
		count[b]++;
	}
	for (ll i=0; i<n; i++)
		if (count[i]==0)
			q.push(i);
	for (ll i=0; i<n; i++){
		if (q.empty()){
			cout << 0;
			return 0;
		}
		ll x=q.front();
		q.pop();
		out.push_back(x);
		for (auto z:vec[x]){
			count[z]--;
			if (count[z]==0) q.push(z);
		}
	}

	for (ll i=0; i<n-1; i++){
		bool b=false;
		for (auto z:vec[out[i]])
			if (z==out[i+1])
				b=true;
		if (!b){
			cout << 2 << '\n';
			for (auto z:out){
				cout << z+1 << ' ';
			}
			cout << '\n';
			for (ll j=0; j<n; j++){
				if (j==i) cout << out[j+1]+1 << ' ';
				else if (j==i+1) cout << out[j-1]+1 << ' ';
				else cout << out[j]+1 << ' ';
			}
			return 0;
		}
	}

	cout << 1 << '\n';
	for (auto z:out){
		cout << z+1 << ' ';
	}
}