#include <iostream>
#include <vector>
#include <deque>

#define ll long long 

using namespace std;

struct element
{
    bool seen,rseen;
    ll in, out;
    vector < ll> sz, rsz;

};

vector <element> x;
ll n, i, j, m, a, b;
deque <ll> res, rres;
bool ok2 = false;
void topo(ll curr)
{
    x[curr].seen = true;
    for (auto& e : x[curr].sz)
    {
        if (!x[e].seen)
        {
             topo(e);
        }
    }
    res.push_front(curr);
}

void rtopo(ll curr)
{
    x[curr].rseen = true;
    for (auto& e : x[curr].rsz)
    {
        if (!x[e].rseen)
        {
           
            rtopo(e);
        }
    }
    rres.push_back(curr);
}
int main()
{
    cin >> n >> m;
    x.resize(n + 1);
    for (i = 1; i <= m; ++i)
    {
        cin >> a >> b;
        x[a].sz.push_back(b);
        x[b].rsz.push_back(a);
        x[a].out++;
        x[b].in++;
    }

    vector <ll> start, rstart;
    for (i = 1; i <= n; ++i)
    {
        if (x[i].in == 0) start.push_back(i);
        if (x[i].out == 0) rstart.push_back(i);
    }

    if (start.size() == 0)
    {
        cout << "0";
        return 0;
    }
    if (start.size() == 1)
    {
        topo(start[0]);
        if (res.size() != n)
        {
            cout << "0";
            return 0;
        }
        rtopo(res.back());

        if (res.size() == rres.size())
        {
            for (i = 0; i < n; ++i)
            {
                if (res[i] != rres[i]) break;
            }
            if (i == n)
            {
                cout << "1\n";
                for (auto& e : res) cout << e << " ";
                return 0;
            }
        }
        for (i = 0; i < min(res.size(), rres.size()); ++i)
        {
            if (res[i] != rres[i]) break;
        }
        cout << "2\n";
        for (auto& e : res) cout << e << " ";
        cout << "\n";
        for (auto& e : rres) cout << e << " ";
        while (i<n && !x[res[i]].rseen)
        {
            cout << res[i] << " ";
            ++i;
        }
        return 0;
    }
    ok2 = true;
    deque <ll> R;
    //for (auto& e : start) R.push_back(e);
    for (auto& e : start)
    {
        while (!res.empty())
        {
            res.pop_front();
            if (!res.empty()) R.push_back(res[0]);
        }
        topo(e);
    }
    res.pop_front();
    if (R.size() + res.size() + start.size() != n)
    {
        cout << "0";
        return 0;
    }

    cout << "2\n";
    for (auto& e : start) cout << e << " ";
    for (auto& e : R) cout << e << " ";
    for (auto& e : res) cout << e << " ";
    cout << "\n";
    cout << start.back() << " ";
    start.pop_back();
    for (auto& e : start) cout << e << " ";
    for (auto& e : R) cout << e << " ";
    for (auto& e : res) cout << e << " ";
    return 0;
}
    

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

*/