#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// const ll MOD = 1e9+7;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

vector<bool> vis;
vector<bool> ki;
vector<int> res;
vector<vector<int>> g;

bool nem = false;
void dfs(int cur) {
	vis[cur] = true;
	for (int i : g[cur]) {
		if (!vis[i]) dfs(i);
		else if (!ki[i]) {
			nem = true;
		}
	}
	ki[cur] = true;
	res.push_back(cur);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k; cin >> n >> k;
    g.resize(n+1); int u, v;
    map<pair<int, int>, bool> m;
    for (int i = 0; i < k; i++) {
    	cin >> u >> v;
    	g[u].push_back(v); m[{u, v}] = true;
    }
    
    vis.resize(n+1, false);
    ki.resize(n+1, false);
    for (int i = 1; i <= n && !nem; i++) if (!vis[i]) dfs(i);
    
    if (nem) {
    	cout << "0\n";
    	return 0;
    }
    
    reverse(res.begin(), res.end());
    vector<int> res2;
    
    for (int i = 1; i < n; i++) {
    	if (!m[{res[i-1], res[i]}]) {
    		res2 = res;
    		swap(res2[i], res2[i-1]);
    		break;
    	}
    }
    
    cout << (res2.size() == 0 ? 1 : 2) << "\n";
    
    for (int i : res) cout << i << " ";
    if (res2.size() == 0) return 0;
    cout << "\n";
    
    for (int i : res2) cout << i << " ";

    return 0;
}