#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<vector<int>> csucsok;
vector<int> bejar;
bool jo = true;

void dfs(int kezd){
    bejar[kezd] = 1;
    for(int x : csucsok[kezd]){
        if(bejar[x] == 1){
            jo = false;
        } else if(bejar[x] == 0){
            dfs(x);
        }
    }
    bejar[kezd] = 2;
}

int main()
{
    cin >> n >> m;
    vector<int> beDB(n + 1, 0);
    csucsok.assign(n + 1, vector<int>(0, 0));
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        csucsok[a].push_back(b);
        beDB[b]++;
    }

    bejar.assign(n, 0);

    for(int i = 0; i < n; i++){
        if(bejar[i] == 0){
            dfs(i);
        }
    }

    if(!jo){
        cout << "0\n";
        return 0;
    }

    queue<int> kezdok;

    for(int i = 1; i <= n; i++){
        if(beDB[i] == 0){
            kezdok.push(i);
        }
    }

    vector<int> topi;

    while(!kezdok.empty()){
        int akt = kezdok.front();
        kezdok.pop();

        for(int x : csucsok[akt]){
            beDB[x]--;
            if(beDB[x] == 0){
                kezdok.push(x);
            }
        }

        topi.push_back(akt);
    }


    bool jo = true;
    int rosszind = 0;
    for(int i = 0; i < n-1; i++){
        bool talal = false;
        for(int x : csucsok[topi[i]]){
            if(x == topi[i + 1]){
                talal = true;
                break;
            }
        }

        if(!talal){
            jo = false;
            rosszind = i;
            break;
        }
    }

    if(jo){
        cout << "1\n";
        for(int x : topi){
            cout << x << " ";
        }

        cout << "\n";
    } else{
        cout << "2\n";
        for(int i = 0; i < n; i++){
            cout << topi[i] << " ";
        }
        cout << "\n";

        for(int i = 0; i < n; i++){
            if(i == rosszind){
                cout << topi[i + 1] << " ";
            } else if(i == rosszind + 1){
                cout << topi[i - 1] << " ";
            } else{
                cout << topi[i] << " ";
            }
        }

        cout << "\n";
    }
}