// UUID: 3882144c-c3a1-4a79-85d6-0cdb19ca6437
// Topologikus sorrend

#include <bits/stdc++.h>
using namespace std;

// declarations
// variables
using ll = long long;
using ld = long double;  // or double, if TL is tight
using str = string;      // yay python!

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<ld, ld>;
#define mp make_pair
#define f first
#define s second

#define tcT template <class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT > using V = vector<T>;
tcT, size_t SZ > using AR = array<T, SZ>;
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<ld>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;
using v2ds = V<V<str>>;
using v2di = V<vi>;
using v2dc = V<V<char>>;

// functions
#define loop(i,a,b) for(int i = (a); i < (b); i++)
#define loopbw(i,a,b) for(int i = (a) - 1; i >= (b); i--)
#define each(a, x) for (auto &a : x)
#define imeach(a,x) for(const auto &a : x)

#define sz(x) int(size(x))
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()

// ----------------------------------------------------------------------

vb volt;
vb fin;
v2di graf;
vi res;

bool impossible = false;

void dfs(int u){

	if(fin[u]) {
		return;
	}

	volt[u] = true;

	each(v,graf[u]){
		if(!volt[v]){
			dfs(v);
		}
		else{
			impossible = true;
			return;
		}
	}

	volt[u] = false;
	res.pb(u);
	fin[u] = true;
}

void solve() {
 
	int n, k;
	cin >> n >> k;

	graf.resize(n+1);
	volt.resize(n+1);
	fin.resize(n+1);

	loop(i,0,k){
		int a,b; cin >> a >> b;
		graf[b].pb(a);
	}

	loop(i,1,n+1){
		if(!volt[i]){
			dfs(i);
		}
	}

	if(impossible) {
		cout << "0";
		return;
	}

	bool nemjooo = false;

	for(int i = 0; i < res.size()-1; i++){

		bool joo = false;
		each(x, graf[res[i+1]]){
			if(x == res[i]){
				joo = true;
				break;
			}
		}

		if(joo) continue;

		if(!joo){
			nemjooo = true;
			cout << "2\n";

			loop(j,0,res.size()){
				if(j == i){
					cout << res[j] << " " << res[j+1] << " ";
					j++;
				}
				else cout << res[j] << " ";
			}
			cout << '\n';
			loop(j,0,res.size()){
				if(j == i){
					cout << res[j+1] << " " << res[j] << " ";
					j++;
				}
				else cout << res[j] << " ";
			}
			break;
		}

	}
	if(!nemjooo){
		cout << "1\n";
		each(x,res){
			cout << x << " ";
		}
	}
	

	// ide ez ele
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
    cout.tie(nullptr);
 
	int t = 1; //cin >> t;
	while(t--) solve();
}