// UUID: 9589e456-0a56-4c07-b046-847d69b772ac
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> graf;
vector<int> been;
vector<int>ts;
bool gatya=false;
int dfs(int x){
    been[x]=1;
    for(int z:graf[x]){
        if(been[z]==1){
            gatya=true;
            break;
        }
        if(been[z]==0)
        dfs(z);
    }
    ts.push_back(x);
    been[x]=2;
    return 0;
}

int main() {
	int n, k; cin>>n>>k;
    graf.resize(n);
    been.resize(n, 0); // 0-nem volt, 1-nem hagyta el, 2-elhagyta
    for(int i=0; i<k; i++){
        int a, b;
        cin>>a>>b;
        a--;
        b--;
        graf[b].push_back(a);
    }
    for(int i=0; i<n; i++){
        if(!been[i])
        dfs(i);
    }
    if(gatya){
        cout<<0;
        return 0;
    }
    for(int i=0; i<n-1; i++){
        if(!(find(graf[ts[i+1]].begin(), graf[ts[i+1]].end(), ts[i]) != graf[ts[i+1]].end())){
            cout<<2<<"\n";
            for(int x:ts){
                cout<<x+1<<" ";
                
            }
            cout<<endl;
            for(int j=0; j<n; j++){
                if(j==i){
                    cout<<ts[j+1]+1<<" "<<ts[j]+1<<" ";
                    j++;
                }
                else
                cout<<ts[j]+1<<" ";
            }
            return 0;
        }
    }
    cout<<1<<endl;
    for(int x:ts){
        cout<<x+1<<" ";
        
    }
    return 0;
}
//a++ és b++!!