#include <bits/stdc++.h>

using namespace std;

int diakszam,emlekszam;
vector<vector<int>> graf;
vector<int> temp;

vector<int> v1;
vector<int> v2;

void rek(int kezd, int szint, vector<int> eljut)
{
    if(graf[kezd].size() == 0 && szint == diakszam)
    {
        /*cout << "1\n" << kezd << " ";
        for(int i = szint-2; i > -1; i--)
        {
            cout << eljut[i] << " ";
        }*/
        if(v1.size() == 0)
        {
            v1 = eljut;
            v1.push_back(kezd);
        }
        else if(v2.size() == 0)
        {
            v2 = eljut;
            v2.push_back(kezd);
            if(v1 == v2){v2.clear();}
        }
    }
    else if(szint < diakszam)
    {
        for(int x : graf[kezd])
        {
            temp = eljut;
            temp.push_back(kezd);
            rek(x,szint+1,temp);
        }
    }
}


int main()
{
    ios::sync_with_stdio(0); cin.tie(0);


    cin >> diakszam >> emlekszam;
    graf.resize(diakszam+1);

    vector<bool> van(diakszam+1);

    int a,b;

    for(int i = 0;i < emlekszam; i++)
    {
        cin >> a >> b;
        graf[b].push_back(a);
        van[a] = true;
    }

    for(int i = 1; i < diakszam+1; i++)
    {
        if(!van[i])
        {
            rek (i,1,{});
            break;
        }
    }

    if(v1.size() == 0)
    {
        cout << 0;
    }
    else if(v2.size() == 0)
    {
        cout << "1\n";
        for(int i = diakszam-1; i > -1; i--)
        {
            cout << v1[i] << " ";
        }
    }
    else
    {
        cout << 2;
        for(int i = diakszam-1; i > -1; i--)
        {
            cout << v1[i] << " ";
        }
        cout << '\n';
        for(int i = diakszam-1; i > -1; i--)
        {
            cout << v2[i] << " ";
        }
    }
}