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

using namespace std;

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

deque <ll> v, poz;
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);
            }
        }
    }
}

bool sorts(const adat& a, const adat& b)
{
    return a.csop < b.csop;
}

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)
    {
        x[i].csp = i;
        if (!x[i].befok)
        {
            szelesseg(i);
        }
    }
    sort(x.begin(), x.end(), sorts);
    if (poz.size() != n)
    {
        cout << "0";
        return 0;
    }
    else
    {
        for (ll i = 2; i <= n; ++i)
        {
            if (x[i].csop == x[i - 1].csop)
            {
                cout << "2\n";
                for (ll j = 1; j <= n; ++j)
                    cout << x[j].csp << " ";
                cout << endl;
                swap(x[i].csp, x[i - 1].csp);
                for (ll j = 1; j <= n; ++j)
                    cout << x[j].csp << " ";
                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

6 4
3 2
2 1
1 5
4 6

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