// UUID: 9e0226fc-5f05-46e9-a2c7-428e7b5a02b3
#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;
        while (!pq.empty()) {
            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;
}