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

const int mxN = 2 * (1e5 + 1);

vector<vector<int> > adj(mxN);
int in[mxN];
bool vis[mxN], rev[mxN];
bool ex;


void dfs (int u) {
	if (ex) {
		return;
	}
	vis[u] = true;
	rev[u] = true;

	for(int x : adj[u]) {
		if (rev[x]) {
			cout << "0\n";
			ex = true;
			return;
		} else if (!vis[x]) {
			dfs(x);
		}
	}

	rev[u] = false;

}


int main() {
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		adj[x].push_back(y);
		in[y]++;
	}
	dfs(1);
	if (ex) {
        return 0;
	}

	vector<int> top;
	queue<int> q;

	for(int i = 1; i <= n; i++) {
		if (in[i] == 0) {
			top.push_back(i);
			q.push(i);
			vis[i] = 1;
		}
	}
	int ind;
	bool flag = false;
	if(top.size() > 1) {
        flag = true;
        ind = 1;
	}

	while(!q.empty()) {
        int v = q.front();
        q.pop();
        int cnt = 0;
        for(int u : adj[v]) {
            in[u]--;
            if (in[u] == 0) {
                q.push(u);
                top.push_back(u);
                cnt++;
            }
        }
        if (cnt >= 2) {
            flag = true;
            ind = top.size();
        }
	}

    if (flag) {
        cout << "2\n";
        for(int x : top) {
            cout << x << ' ';
        }
        cout << endl;
        swap(top[ind], top[ind-1]);
        for(int x : top) {
            cout << x << ' ';
        }
        cout << endl;
    } else {
        cout << "1\n";
        for(int x : top) {
            cout << x << ' ';
        }
        cout << endl;
    }
	return 0;
}