// UUID: c11e3124-dd2e-4cfb-aad7-42e0df5b4353
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> graf;
vector<int> vis;
bool kor=false;
vector<int> ans;

void dfs(int x){
    vis[x]=1;
    for (int i:graf[x]){
        if (vis[i]==0) dfs(i);
        else if (vis[i]==1) kor=true;
    }
    ans.push_back(x);
    vis[x]=2;
}

int main() {
	int n,k; cin>>n>>k;
    int a,b; 
    graf.resize(n);
    vis.resize(n,0);
    for (int i=0; i<k; i++){
        cin>>a>>b;
        a--; b--;
        graf[a].push_back(b);
    }
    for (int i=0; i<n; i++){
        if (vis[i]==0) dfs(i);
    }
    if (kor) cout<<0<<endl;
    else{ 
        int ind=-1;
        reverse(ans.begin(),ans.end());
        for (int i=0; i<n-1; i++){
            bool g=false;
            for (int j:graf[ans[i]]){
                if (j==ans[i+1]){
                    g=true;
                }
            }
            if (!g) ind=i;
        }
        if (ind==-1){
            cout<<1<<endl;
            for (int i:ans) cout<<i+1<<" ";
        }
        else {
            cout<<2<<endl;
            for (int i=0; i<n; i++){
                cout<<ans[i]+1<<" ";
            } 
            cout<<endl;
            swap(ans[ind],ans[ind+1]);
            for (int i=0; i<n; i++){
                cout<<ans[i]+1<<" ";
            }
        }
    }
}