// UUID: 0e0f7c8d-d0fc-4ce7-af25-3b358c20f8f6
#include <bits/stdc++.h>
#include <queue>
#include <vector>
using namespace std;


int main() {
	int n, m; cin >> n >> m;
    vector<vector<int>> g(n+1, vector<int>(n+1, 0));
    vector<int> fokszam(n+1, 0);
    vector<int> ans;
    for (int i=0;i<m;i++){
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        fokszam[b]++;
    }
    queue<int> q;
    for (int i=0;i<=n;i++) {
        if (!fokszam[i]) {
            q.push(i);
        }
    } 
        // cout << fokszam[i];
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ans.push_back(u);
        for (int i: g[u]) {
            fokszam[i]--;
            if (!fokszam[i]){
                q.push(i);
            } 
        }

        // cout << u << '\n';
    }
    // for(int i: fokszam) {
    //     cout << i << '\n';
    // }
    if (ans.size()-1 != n) {     
        cout << 0;
        return 0;
    }
    pair<int, int> felcserel = {0, 0};
    for (int i=1;i<n;i++) {
            bool benne = false;
            for (int j: g[ans[i]]) {
                if (j == ans[i+1]) benne = 1; 
            } 
            if (!benne) {
                felcserel.first = ans[i];
                felcserel.second = ans[i+1];
                // cout << felcserel.first << ' ' << felcserel.second << "ab\n";
                break;
            }
        }
    cout << (felcserel.second ? 2: 1) << endl;
    for(int i: ans) {
        if (i) cout << i <<' ';
    }
    if (!felcserel.second) return 0;
    cout <<'\n';
    // cout << felcserel.first << ' ' << felcserel.second;

    // cout <<'\n';

    for(int i: ans) {
        if (i == felcserel.first) cout << felcserel.second << ' ';
        else if (i == felcserel.second) cout << felcserel.first << ' ';
        else if(i) cout << i <<' ';
    }
}