// UUID: fde2d36f-f6d7-4fc5-9bf7-2397789c64f3
#include <bits/stdc++.h>
#include <vector>
#include <numeric>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k; cin >> n >> k;
    vector<vector<int>> g(n + 1);
    vector<int> beelek(n + 1, 0);
    vector<vector<int>> solutions(2);
    for (int i = 0; i < k; i++) {
        int a, b; cin >> a >> b;
        g[b].push_back(a);
        beelek[b]++;
    }
    beelek[0] = -1;
    while (!all_of(begin(beelek), end(beelek), [](int i) { return i < 0; })) {
        vector<int> forrasok;
        for (int i = 1; i <= n; i++) {
            if (beelek[i] == 0) {
                forrasok.push_back(i);
            }
        }
        if (forrasok.size() == 0) {
            cout << 0; return 0;
        }
        else {
            for (int i = 0; i < forrasok.size(); i++) {
                solutions[0].push_back(forrasok[i]);
                solutions[1].push_back(forrasok[forrasok.size() - 1 - i]);
            }
        }
        for (int j : forrasok) {
            beelek[j] = -1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j : forrasok) {
                if (find(g[i].begin(), g[i].end(), j) != g[i].end()) {
                    beelek[i]--;
                }
            }
        }
    }
    int o = 1;
    for(int i = 0; i < n; i++){
        if(solutions[0][i] != solutions[1][i]) {
            o = 2; break;
        }
    }
    cout<<o<<endl;
    for(int i:solutions[0]){
        cout<<i<<" ";
    }
    cout<<endl;
    if(o == 2){
        for(int i:solutions[1]){
            cout<<i<<" ";
        }
    }
}