// UUID: 02115b33-678d-4593-b787-34799210c43b
#include <bits/stdc++.h>
using namespace std;

void solve() {
    int v, e;
    cin >> v >> e;

    vector<int> res;
    vector<vector<int>> adj(v + 1);
    vector<int> ind(v + 1, 0);
    int k = -1;

    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        ind[b]++;
    }

    queue<int> q;
    for (int i = 1; i <= v; i++) {
        if (ind[i] == 0) q.push(i);
    }

    while (!q.empty()) {
        if (q.size() > 1) k = res.size();

        int curr = q.front();
        q.pop();
        res.push_back(curr);

        for (int i : adj[curr]) {
            ind[i]--;
            if (ind[i] == 0) q.push(i);
        }
    }

    if (k == -1) {
        cout << 1 << "\n";
        for (int i : res) cout << i << ' ';
    } else {
        cout << 2 << "\n";
        for (int i : res) cout << i << ' ';
        swap(res[k], res[k+1]);
        for (int i : res) cout << i << ' ';
    }

    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}