#include <bits/stdc++.h>

using namespace std;


vector<vector<int>> v;
vector<int> top, top2, color;
bool circle = false;
vector<bool> seen;


void dfs1(int x){
    if (color[x] == 2){circle = true; return;}
    if (color[x] == 3) return;
    color[x] = 2;

    for (int i : v[x]){
        dfs1(i);
    }

    color[x] = 3;
}

void dfs2(int x){
    if (seen[x]) return;
    seen[x] = true;

    for (int i : v[x]){
        dfs2(i);
    }

    top.push_back(x);

}


void dfs3(int x){
    if (seen[x]) return;
    seen[x] = true;

    for (int i : v[x]){
        dfs3(i);
    }

    top2.push_back(x);

}


int main(){


    int n, k; cin >> n >> k;
    v.assign(n+1, {});
    seen.assign(n+1, false);
    color.assign(n+1, 1);


    for (int i = 0; i < k; i++){

        int a, b; cin >> a >> b;
        v[a].push_back(b);

    }


    for (int i = 1; i <= n; i++){
        dfs1(i);
    }

    if (circle){
        cout << 0;
        return 0;
    }


    for (int i = 1; i <= n; i++){
        dfs2(i);
    }

    reverse(top.begin(), top.end());
    seen.assign(n+1, false);


    for (int i = n; i >= 1; i--){
        dfs3(i);
    }


    reverse(top2.begin(), top2.end());

    bool one = true;

    for (int i = 0; i < n; i++){
        if (top[i] != top2[i]) one = false;
    }

    if (one){
        cout << 1 << endl;
        for (int i : top){
            cout << i << " ";
        }
        return 0;
    }

    cout << 2 << endl;

    for (int i : top) cout << i << " ";

    cout << endl;

    for (int i : top2) cout << i << " ";


    return 0;
}