// UUID: b322a507-791a-4fac-9c53-108b710c39d5
#include <bits/stdc++.h>
using namespace std;

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

    int N, K;
    cin >> N >> K;

    vector<vector<int>> g(N + 1);
    vector<int> indeg(N + 1, 0);

    for (int i = 0; i < K; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        indeg[b]++;
    }

    // topologikus rendezés (Kahn algoritmus)
    queue<int> q;
    for (int i = 1; i <= N; i++) {
        if (indeg[i] == 0) q.push(i);
    }

    vector<int> order;
    bool multiple = false;

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

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

    if (!multiple) {
        cout << 1 << "\n";
        for (int i = 0; i < N; i++) {
            cout << order[i] << (i + 1 == N ? '\n' : ' ');
        }
    } else {
        cout << 2 << "\n";
       
        for (int i = 0; i < N; i++) {
            cout << order[i] << (i + 1 == N ? '\n' : ' ');
        }
                vector<int> indeg2(N + 1, 0);
        for (int i = 1; i <= N; i++)
            for (int v : g[i]) indeg2[v]++;
        priority_queue<int, vector<int>, greater<int>> pq; 
        for (int i = 1; i <= N; i++)
            if (indeg2[i] == 0) pq.push(i);

        vector<int> order2;
        bool skipped = false;
        while (!pq.empty()) {
            if (pq.size() > 1 && !skipped) {
                
                int first = pq.top(); pq.pop();
                int second = pq.top(); pq.pop();
                order2.push_back(second);
                for (int v : g[second]) {
                    indeg2[v]--;
                    if (indeg2[v] == 0) pq.push(v);
                }
                pq.push(first);
                skipped = true;
            } else {
                int u = pq.top(); pq.pop();
                order2.push_back(u);
                for (int v : g[u]) {
                    indeg2[v]--;
                    if (indeg2[v] == 0) pq.push(v);
                }
            }
        }
        for (int i = 0; i < N; i++) {
            cout << order2[i] << (i + 1 == N ? '\n' : ' ');
        }
    }

    return 0;
}