#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct gyerek{
    int nagyobb=0;
    vector<int> kisebb;
};

gyerek a[200000];
int n, x, y, k, s[200000];
bool csere=0;
pair<int, int> cs;
queue<int> q;
int main()
{
    cin >> n >> k;
    for(int i=0; i<k; i++){
        cin >> x >> y;
        x--;
        y--;
        a[y].kisebb.push_back(x);
        a[x].nagyobb++;
    }
    for(int i=0; i<n; i++){
        if(a[i].nagyobb==0){
            q.push(i);
        }
    }
    for(int i=0; i<n; i++){
        if(q.empty()){
            cout << 0;
            return 0;
        }
        s[i]=q.front();
        q.pop();
        if(!q.empty()){
            csere=1;
            cs.first=i;
            cs.second=i+1;
        }
        for(auto& it:a[s[i]].kisebb){
            a[it].nagyobb--;
            if(a[it].nagyobb==0){
                q.push(it);
            }
        }
    }
    if(!csere){
        cout << 1 << '\n';
        for(int i=n-1; i>=0; i--){
            cout << s[i]+1 << ' ';
        }
    }
    else{
        cout<< 2 << '\n';
        for(int i=n-1; i>=0; i--){
            cout << s[i]+1 << ' ';
        }
        swap(s[cs.first], s[cs.second]);
        cout << '\n';
        for(int i=n-1; i>=0; i--){
            cout << s[i]+1 << ' ';
        }
    }


    return 0;
}