// UUID: 09555e85-a43b-4c6b-84d1-8053143949c5
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

vector<int> r;
map<int, bool> m;
bool cannot = false;

void dfs(vector<vector<int>>& g, vector<bool>& vis, int cur) {
    vis[cur] = true;
    for (auto& e : g[cur]) {
        if (!vis[e]) {
            dfs(g, vis, e);
        } else {
            if (!m[e]) {
                cannot = true;
            }
        }
    }
    r.push_back(cur);
    m[cur] = 1;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k; cin >> n >> k;
    vector<vector<int>> g(n);
    vector<vector<bool>> adj(n, vector<bool>(n, 0));
    for (int i = 0; i < k; i++) {
        int a, b; cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        adj[a][b] = 1;
    }

    vector<bool> vis(n);
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            dfs(g, vis, i);
        }
    }

    if (cannot) {
        cout << "0\n"; return 0;
    }

    int swappable = -1;
    for (int i = 1; i < r.size(); i++) {
        if (!adj[r[i]][r[i-1]]) {
            swappable = i;
        }
    }

    if (swappable == -1) {
        cout << "1\n";
    } else {
        cout << "2\n";
    }

    for (int i = r.size()-1; i >= 0; i--) {
        cout << r[i]+1 << " ";
    }

    if (swappable != -1) {
        int helper = r[swappable-1];
        r[swappable-1] = r[swappable];
        r[swappable] = helper;
        cout << "\n";
        for (int i = r.size()-1; i >= 0; i--) {
            cout << r[i]+1 << " ";
        }
    }
	
    return 0;
}