// UUID: 2a20c6bd-6ebe-4414-9630-9df6a5844397
#include <bits/stdc++.h>
using namespace std;

int n,m,cycle=0;
vector<vector<int>> g;
vector<int> st,topo;

void dfs(int u){
    st[u]=1;
    for(int v:g[u]){
        if(st[v]==0) dfs(v);
        else if(st[v]==1) cycle=1;
    }
    st[u]=2;
    topo.push_back(u);
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    g.assign(n+1,{});
    for(int i=0,a,b;i<m;i++){
        cin>>a>>b;
        g[a].push_back(b);
    }
    st.assign(n+1,0);
    for(int i=1;i<=n;i++) if(!st[i]) dfs(i);
    if(cycle){ cout<<0<<"\n"; return 0; }

    reverse(topo.begin(),topo.end());

    // gyors él-ellenőrzéshez set vagy unordered_set
    vector<unordered_set<int>> E(n+1);
    for(int u=1;u<=n;u++) for(int v:g[u]) E[u].insert(v);

    int sw=-1;
    for(int i=0;i<n-1;i++){
        int u=topo[i], v=topo[i+1];
        if(!E[u].count(v)){ sw=i; break; }
    }

    if(sw==-1){
        cout<<1<<"\n";
        for(int i=0;i<n;i++) cout<<topo[i]<<" \n"[i==n-1];
    }else{
        cout<<2<<"\n";
        for(int i=0;i<n;i++) cout<<topo[i]<<" \n"[i==n-1];
        swap(topo[sw], topo[sw+1]);
        for(int i=0;i<n;i++) cout<<topo[i]<<" \n"[i==n-1];
    }
}