#include <iostream>
#include <queue>
#include <algorithm>
#define ll long long

using namespace std;

struct adat
{
    bool lat = false;
    ll csop = 1, befok = 0;
    vector <ll> sz;
};
vector <adat> x;

deque <ll> v, poz;
bool kor = false;
void szelesseg(ll csp)
{
    v.push_front(csp);
    if(!x[csp].lat)
        poz.push_front(csp);
    while (!v.empty())
    {
        ll akt = v.front();
        v.pop_front();
        x[akt].lat = true;
        for (auto& e : x[akt].sz)
        {
            x[e].befok--;
            if (!x[e].befok)
            {
                v.push_front(e);
                x[e].csop = x[akt].csop + 1;
                poz.push_back(e);
            }
        }
    }
}

int main()
{
    ll n, k;
    cin >> n >> k;
    x.resize(n + 1);
    for (ll i = 1; i <= k; ++i)
    {
        ll cs1, cs2;
        cin >> cs1 >> cs2;
        x[cs1].sz.push_back(cs2);
        x[cs2].befok++;
    }

    for (ll i = 1; i <= n; ++i)
    {
        if (!x[i].befok)
        {
            szelesseg(i);
        }
    }
    if (poz.size() != n)
    {
        cout << "0";
        return 0;
    }
    else
    {
        for (ll i = 1; i < n; ++i)
        {
            if (x[poz[i - 1]].csop == x[poz[i]].csop)
            {
                cout << "2\n";
                for (auto& e : poz)
                    cout << e << " ";
                cout << endl;
                swap(poz[i], poz[i - 1]);
                for (auto& e : poz)
                    cout << e << " ";
                return 0;
            }
        }
        cout << "1\n";
        for (auto& e : poz)
            cout << e << " ";
    }

    return 0;
}
/*
5 9
3 1
3 5
3 4
4 2
3 2
1 4
1 2
1 5
5 4

5 3
2 1
3 2
1 5

4 4
1 2
2 3
3 4
4 2
*/