// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

vector<int> vis;

bool dfs(vector<vector<int>>& v, int node){
    vis[node]=1;
    bool jo=true;
    for(int i : v[node]){
        if(vis[i]==1)return false;
        else if(vis[i]==0){
            jo&=dfs(v,i);
        }
    }
    vis[node]=2;
    return jo;
}

int main() {
    int n,k;cin>>n>>k;
    vector<vector<int>> v(n);
    vis.resize(n);
    vector<int> befok(n),kifok(n);
    for(int i = 0;i<k;i++){
        int a,b;cin>>a>>b;
        v[--a].push_back(--b);
        kifok[a]++;
        befok[b]++;
    }
    bool jo=true;
    for(int i = 0;i<n;i++){
        if(vis[i]==0){
            if(!dfs(v,i)){
                jo=false;
                break;
            }
        }
    }
    if(jo==false){
        cout<<0<<endl;
        return 0;
    }
    int mon=0;
    deque<int> top1,bf;
    vector<int> volt(n);
    for(int i = 0;i<n;i++){
        if(befok[i]==0&&mon!=0&&!volt[i])bf.push_back(i);
        if(befok[i]==0&&mon<1){
            mon++;
            queue<int> q;
            q.push(i);
            while(!q.empty()){
                int node=q.front();
                q.pop();
                volt[node]=1;
                if(mon==1){
                    top1.push_back(node);
                }
                for(int u : v[node]){
                    befok[u]--;
                    if(befok[u]==0){
                        q.push(u);
                    }
                }
            }
        }
    }
    if(top1.size()==n){
        cout<<1<<endl;
        for(int i : top1)cout<<i+1<<' ';
    }
    else{
        vector<int> top2;
        queue<int> q;
        for(int i : bf)q.push(i);
        while(!q.empty()){
            int node=q.front();
            q.pop();
            top2.push_back(node);
            for(int u : v[node]){
                befok[u]--;
                if(befok[u]==0){
                    q.push(u);
                }
            }
        }
        cout<<2<<endl;
        for(int i : top1)cout<<i+1<<' ';
        for(int i : top2)cout<<i+1<<' ';
        cout<<endl;
        for(int i : top2)cout<<i+1<<' ';
        for(int i : top1)cout<<i+1<<' ';

    }
}