#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

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

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

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

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

bool topo_sorrend(int u, std::vector<int> &allapot, std::vector<int> &sorrend, const Graf &g) {
    if (allapot[u] == 1) {
        return false;
    }

    if (allapot[u] == 2) {
        return true;
    }

    allapot[u] = 1;
    for (const int v: g[u]) {
        if (!topo_sorrend(v, allapot, sorrend, g)) {
            return false;
        }
    }

    allapot[u] = 2;
    sorrend.push_back(u);

    return true;
}

bool van_el(int u, int v, const Graf &g) {
    return find(g[u].begin(), g[u].end(), v) != g[u].end();
}

void sorrend_ki(const std::vector<int> &sorrend) {
    using std::cout;

    for (const auto i: sorrend) {
        cout << i + 1 << ' ';
    }
    cout << '\n';
}

void tornasor_ki(int n, const Emlekek &emlekek) {
    Graf g(n);
    for (const auto [a, m]: emlekek) {
        g[a - 1].push_back(m - 1);
    }

    std::vector<int> allapot(n), sorrend;
    for (int u = 0; u < n; u++) {
        if (allapot[u] != 0) {
            continue;
        }

        if (!topo_sorrend(u, allapot, sorrend, g)) {
            sorrend.clear();
            break;
        }
    }

    using std::cout;

    if (sorrend.empty()) {
        cout << "0\n";

    } else {
        reverse(sorrend.begin(), sorrend.end());

        int i;
        for (i = 1; i < n && van_el(sorrend[i - 1], sorrend[i], g); i++) { }

        cout << (i == n ? '1' : '2') << '\n';

        sorrend_ki(sorrend);
        if (i < n) {
            std::swap(sorrend[i - 1], sorrend[i]);
            sorrend_ki(sorrend);
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    Emlekek emlekek;
    beolvas(n, emlekek);
    tornasor_ki(n, emlekek);

    return 0;
}