// UUID: ebfa39d1-1e41-4cf7-889d-90d09e84cd69
#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;
    int multi_where = -1;

    while (!q.empty()) {
        if (q.size() > 1) {
            multiple = true;
            multi_where = order.size();
        }
        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' : ' ');
        }
        swap(order[multi_where], order[multi_where + 1]);
        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;
}