#include <iostream>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> graph;
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    graph.resize(n+1);
    int x,y;
    vector<int> indeg(n+1,0);
    for(int i=0;i<m;i++)
        {
        cin>>x>>y;
        indeg[y]++;
        graph[x].push_back(y);
        }
    bool s=false;
    pair<int,int> swappable;
    queue<int> q;
    vector<int> topo;
    for(int i=1;i<=n;i++)if(!indeg[i]){q.push(i);topo.push_back(i);}
    if(topo.size()>1)
        {
        s=true;
        swappable.first=0;
        swappable.second=1;
        }
    while(q.size())
        {
        int cnt=0;
        int v=q.front();q.pop();
        for(int x:graph[v])
            {
            indeg[x]--;
            if(indeg[x]==0)
                {
                q.push(x);
                cnt++;
                topo.push_back(x);
                if(!s && cnt>1)
                    {
                    s=true;
                    swappable.first=topo.size()-2;
                    swappable.first=topo.size()-1;
                    }
                }
            }
        }
    if(topo.size()!=n)cout<<0;
    else
        {
        if(s==false)
            {
            cout<<1<<"\n";
            for(int x:topo)cout<<x<<" ";
            }
        else
            {
            cout<<2<<"\n";
            for(int x:topo)cout<<x<<" ";
            cout<<"\n";
            for(int i=0;i<n;i++)
                {
                if(i==swappable.first)
                    {
                    cout<<topo[swappable.second]<<" ";
                    cout<<topo[swappable.first]<<" ";
                    i++;
                    }
                else cout<<topo[i]<<" ";
                }
            }
        }
    return 0;
}