// UUID: 376ccf34-33d2-4c8d-9ca9-75225d5fc552
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200000 + 5;
vector<int> lista[MAXN];
int bejovo[MAXN];
int allapot[MAXN];
vector<int> top;
int N, K;
bool kor = false;

void dfs(int u) {
    allapot[u] = 1;
    for (int v : lista[u]) {
        if (allapot[v] == 0) dfs(v);
        else if (allapot[v] == 1) kor = true;
    }
    allapot[u] = 2;
    top.push_back(u);
}

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

    cin >> N >> K;
    for (int i = 0; i < K; i++) {
        int a, b;
        cin >> a >> b;
        lista[a].push_back(b);
        bejovo[b]++;
    }
    for (int i = 1; i <= N; i++) {
        if (allapot[i] == 0) dfs(i);
    }
    if (kor) {
        cout << 0 << "\n";
        return 0;
    }
    vector<int> bejovo2(bejovo, bejovo + N + 1);
    queue<int> q;
    for (int i = 1; i <= N; i++) if (bejovo2[i] == 0) q.push(i);

    vector<int> order;
    bool tobb = false;

    while (!q.empty()) {
        if (q.size() > 1) tobb = true;
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : lista[u]) {
            if (--bejovo2[v] == 0) q.push(v);
        }
    }

    if ((int)order.size() != N) {
        cout << 0 << "\n";
        return 0;
    }

    if (tobb) {
        cout << 2 << "\n";
        for (int x : order) cout << x << " ";
        cout << "\n";
        vector<int> alt = order;
        for (int i = 0; i + 1 < N; i++) {
            int a = alt[i], b = alt[i+1];
            if (find(lista[a].begin(), lista[a].end(), b) == lista[a].end()) {
                swap(alt[i], alt[i+1]);
                break;
            }
        }
        for (int x : alt) cout << x << " ";
        cout << "\n";
    } else {
        cout << 1 << "\n";
        for (int x : order) cout << x << " ";
        cout << "\n";
    }
}