// UUID: f04a41c2-b6de-4605-a517-a7f3bdab95d2
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, m;
    cin>>n>>m;
    vector<vector<int>>szl(n+1);
    vector<int>befok(n+1, 0);
    queue<int>nullasok;
        for(int i=0; i<m; i++){
        int a, b;
        cin>>a>>b;
        szl[a].push_back(b);
        befok[b]++;
    }
    for(int i=1; i<n+1; i++){
        if(befok[i]==0) {
            nullasok.push(i);
        }
    }
    vector<int>megold;
    int vmi=-1;
    while(!nullasok.empty()){
        int j=nullasok.front();
        megold.push_back(j);
        nullasok.pop();
        if(!nullasok.empty()){
           vmi=megold.size();
        }
        for(int sz : szl[j]){
            befok[sz]--;
            if(befok[sz]==0) nullasok.push(sz);
        }
    }
    if(vmi!=-1 && megold.size()==n){
        cout<<2<<endl;
        for(int x: megold)cout<<x<<" ";
        cout<<endl;
        for(int i=0; i<vmi-1; i++)cout<<megold[i]<<" ";
        cout<<megold[vmi]<<" "<<megold[vmi-1]<<" ";
        for(int i=vmi+1; i<megold.size(); i++)cout<<megold[i]<<" ";
    }
    else{
        if(megold.size()==n){
            cout<<1<<endl;
            for(int x : megold)cout<<x<<" ";
        }
        else cout<<0<<endl;

    }
    
}