#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using Emlekek = std::vector<std::pair<int, int>>;

void beolvas(std::istream &be, int &n, Emlekek &emlekek) {
    be >> n;

    int k;
    be >> k;

    emlekek.resize(k);
    for (auto &e : emlekek) {
        be >> e.first >> e.second;
    }
}

using Graf = std::vector<std::vector<int>>;

enum class Allapot {
    Felderitetlen,
    FeldolgozasAlatt,
    Feldologozott
};

bool dfs(int akt, const Graf &g, std::vector<Allapot> &allapot, std::vector<int> &sorrend) {
    switch (allapot[akt]) {

    case Allapot::Felderitetlen:
        allapot[akt] = Allapot::FeldolgozasAlatt;
        for (auto sz : g[akt]) {
            if (!dfs(sz, g, allapot, sorrend)) {
                return false;
            }
        }
        sorrend.push_back(akt + 1);
        allapot[akt] = Allapot::Feldologozott;
        return true;

    case Allapot::FeldolgozasAlatt:
        return false;

    case Allapot::Feldologozott:
        return true;
    }

    return false;
}

bool van_ele(const Graf &g, int honnan, int hova) {
    return std::find(g[honnan].cbegin(), g[honnan].cend(), hova) != g[honnan].cend();
}

void sorrend_ki(const std::vector<int> &sorrend) {
    std::copy(sorrend.crbegin(), sorrend.crend(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
}

void feldolgoz(int n, const Emlekek &emlekek) {
    Graf g(n);
    for (const auto &e : emlekek) {
        g[e.first - 1].push_back(e.second - 1);
    }

    std::vector<Allapot> allapot(n, Allapot::Felderitetlen);
    std::vector<int> sorrend;
    for (auto i = 0; i < n; i++) {
        if (allapot[i] == Allapot::Felderitetlen) {
            if (!dfs(i, g, allapot, sorrend)) {
                sorrend.clear();
                break;
            }
        }
    }

    using std::cout;

    if (!sorrend.empty()) {
        int i;
        for (i = n - 1; i > 0 && van_ele(g, sorrend[i] - 1, sorrend[i - 1] - 1); --i) {}
        if (i == 0) {
            cout << "1\n";
            sorrend_ki(sorrend);

        } else {
            cout << "2\n";
            sorrend_ki(sorrend);
            std::swap(sorrend[i], sorrend[i - 1]);
            sorrend_ki(sorrend);
        }

    } else {
        cout << "0\n";
    }
}

int main() {
    int n;
    Emlekek e;
    beolvas(std::cin, n, e);

    feldolgoz(n, e);

    return 0;
}