// UUID: 154580ed-3e5c-4730-adb3-070d65e6aff1
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> edges;
vector<int> vis, ans;
bool poss = true, un = true;

void dfs(int node) {
    vis[node] = 1;
    for (int x : edges[node]) {
        if (vis[x] == 1) poss = false;
        else if (!vis[x]) dfs(x);
    }
    vis[node] = 2;
    if (ans.empty()) {
        ans.push_back(node);
        return;
    }
    bool b = false;
    for (int x : edges[node]) if (x == ans.back()) b = true;
    if (!b) un = false;
    ans.push_back(node);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, k;
    cin >> n >> k;
    edges.resize(n);
    vis.assign(n, 0);
    while (k--) {
        int a, m;
        cin >> a >> m;
        a--; m--;
        edges[m].push_back(a);
    }
    for (int i = 0; i < n; i++) if (!vis[i]) dfs(i);
    if (!poss) {
        cout << 0;
        return 0;
    }
    if (un) {
        cout << 1 << "\n";
        for (int x : ans) cout << x + 1 << " ";
        return 0;
    }
    cout << 2 << "\n";
    for (int x : ans) cout << x + 1 << " ";
    cout << "\n";
    for (int i = 1; i < n; i++) {
        bool b = false;
        for (int x : edges[ans[i]]) if (x == ans[i - 1]) b = true;
        if (!b) {
            swap(ans[i], ans[i - 1]);
            break;
        }
    }
    for (int x : ans) cout << x + 1 << " ";
    return 0;
}