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

list<int> a;
list<int> mx;
vector<vector<int>> magas(200001);
bool kor = false;
vector<bool> kors(200001, 0);
void dsearch(int v)
{
    if(kors[v]) kor = true;
    else if(kor) return;
    else
    {
        a.push_back(v);
        if(magas[v].size() == 0)
        {
            if(mx.size() < a.size())
            {
                mx = a;
            }
        }
        else
        {
                kors[v] = true;
        for(int i = 0; i< magas[v].size(); i++)
            {
                if(kor) break;
                dsearch(magas[v][i]);

            }
                kors[v] = false;

        }
        a.erase(prev(a.end()));
    }
}
int main()
{   iostream::sync_with_stdio(0);
    cin.tie();
    int n, k;
    cin >> n >> k;
    int m, v;
    set<int> e;
    set<int> x;
    for(int i = 0; i < n; i++)
    {
        x.insert(i);
        e.insert(i);
    }
    for(int i = 0; i < k; i++)
    {
        cin >> m >> v;
        magas[v-1].push_back(m-1);
        e.insert(v-1);
        e.erase(m-1);
        x.erase(v-1);
        x.erase(m-1);
    }
    for(set<int>::iterator itr = e.begin(); itr != e.end(); ++itr)
    {
    dsearch(*itr);
    }
    if(kor)
        cout << "0";
    else if(mx.size() == n)
    {
    cout << "1\n";
    for(list<int>::reverse_iterator itr = mx.rbegin(); itr != mx.rend(); ++itr)
    {
        cout << *itr+1 << " ";
    }
    }
    else
    {
        cout << "2\n";
        for(set<int>::reverse_iterator itr = x.rbegin(); itr != x.rend(); ++itr)
    {
        cout << *itr+1 << " ";
    }
    for(list<int>::reverse_iterator itr = mx.rbegin(); itr != mx.rend(); ++itr)
    {
        cout << *itr+1 << " ";
    }
     cout << "\n";

    for(list<int>::reverse_iterator itr = mx.rbegin(); itr != mx.rend(); ++itr)
    {
        cout << *itr+1 << " ";
    }
         for(set<int>::iterator itr = x.begin(); itr != x.end(); ++itr)
    {
        cout << *itr+1 << " ";
    }
    }
}