// UUID: 3dc890d6-a8c7-4e79-90d8-b2bc6abb95d0
#include <bits/stdc++.h>

#define f(i, n) for(int i = 0; i < n; i++)
#define fr(i, n, s) for(int i = s; i >= n; i--)
#define fs(i, n, s) for(int i = s; i < n; i++)
#define all(v) (v).begin(), (v).start()
#define rall(v) (v).rbegin(), (v).rend()

using namespace std;

template <typename T>
using v = vector<T>;

typedef long long ll;
typedef unsigned u;
typedef unsigned short us;
typedef unsigned long long ull;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, k;
    cin >> n >> k;

    v<set<int>> s(n), t(n);
    v<int> cnt(n);
    f(i, k) {
        int a, b;
        cin >> a >> b;
        a--; b--;

        s[b].insert(a); cnt[b]++;
        t[a].insert(b);
    }

    v<int> end, start;
    f(i, n) {
        if (t[i].empty()) end.push_back(i);
        if (s[i].empty()) start.push_back(i);
    }

    if (end.empty() || start.empty()) {
        cout << 0;
        return 0;
    }

    pair<int, int> idk = {-1, -1};
    v<int> crnt = start, sol, next;
    while (!crnt.empty()) {
        //if (crnt.size() != 1) {
        //    idk = {crnt[0], crnt[1]};
        //}
        for (int i : crnt) {
            for (int j : t[i]) {
                if (--cnt[j] == 0) next.push_back(j);
                else if (cnt[j] < 0) {
                    cout << 0;
                    return 0;
                }
            }
            if (!sol.empty() && !t[sol[sol.size() - 1]].count(i)) idk = {sol[sol.size() - 1], i};
            sol.push_back(i);
        }
        crnt = next; next.clear();
    }

    if (idk.first == -1) {
        cout << 1 << endl;
        for (int i : sol) cout << i + 1 << ' ';
    } else {
        cout << 2 << endl;
        for (int i : sol) cout << i + 1 << ' ';
        cout << endl;

        for (int i : sol) {
            if (i == idk.first) cout << idk.second + 1 << ' ';
            else if (i == idk.second) cout << idk.first + 1 << ' ';
            else cout << i + 1 << ' ';
        }
    }

    return 0;
}