#include <bits/stdc++.h>

using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

int n,k;
vector<int>befok;
vector<vector<int>>g;
vector<bool>vis;
vector<int>mo;
int db=0;
bool ketto=false;
int l,r;

int bfs()
{
    queue<int>q;
    for(int i=1;i<=n;i++)
    {
        if(befok[i]==0)
        {
            q.push(i);
        }
    }
    if(q.size()==0)
    {
        return -1;
    }else
    {
        if(q.size()>=2)
        {
            ketto=true;
            l=0,r=1;
        }
        while(!q.empty())
        {
            int v=q.front();
            q.pop();
            mo.push_back(v);
            for(int x:g[v])
            {
                befok[x]--;
                int db1=0;
                if(befok[x]==0 && !vis[x])
                {
                    q.push(x);
                    vis[x]=true;
                    db1++;
                    if(db1>1 && !ketto)
                    {
                        ketto=true;
                        l=q.size()-2;
                        r=q.size()-1;
                    }
                }
            }
            db++;
        }
        if(db<n)
        {
            return -1;
        }
        if(!ketto)
        {
            return 1;
        }
        return 2;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k;
    befok.resize(n+1,0);
    g.resize(n+1);
    vis.resize(n+1,0);
    db=0;
    for(int i=1;i<=k;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        befok[v]++;
    }
    int m=bfs();
    if(m==-1)
    {
        cout<<0<<'\n';
    }else if(m==1)
    {
        cout<<1<<'\n';
        for(int x:mo)
        {
            cout<<x<<" ";
        }
    }else
    {
        cout<<2<<'\n';
        for(int x:mo)
        {
            cout<<x<<" ";
        }
        cout<<'\n';
        for(int i=0;i<=n-1;i++)
        {
            if(i!=l && i!=r)
            {
                cout<<mo[i]<<" ";
            }else if(i==l)
            {
                cout<<mo[r]<<" ";
            }else if(i==r)
            {
                cout<<mo[l]<<" ";
            }
        }
    }
    return 0;
}