// UUID: aac1058a-879d-4ca1-b480-442cf8f71412
#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> topology;
vector<bool> vis;   
vector<vector<int>> adj;
vector<int> in_nodes;
vector<bool> active;

void dfs(int v){
    vis[v] = true;
    //cout << "belép: " << v << '\n';
    for(auto x : adj[v]){
        if(!vis[x]){
            dfs(x);
        }else if(active[x]){
            cout << 0 << '\n';
            exit(0);
        }else{
        }
    }
    //cout << "elhagy: " << v << '\n';
    active[v] = false;
    topology.push_back(v);
}

bool is_edge(int v1, int v2){
    for(auto x : adj[v1]) if(x == v2) return true;
    for(auto x : adj[v2]) if(x == v1) return true;
    return false;
}

int main() {
	cin >> n >> k;
    vis.resize(n+1, false);
    active.resize(n+1, true);
    in_nodes.resize(n+1, 0);
    adj.resize(n+1, vector<int>());
    for(int i=1;i<=k;i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        in_nodes[b]++;
    }
    for(int i=1;i<=n;i++){
        if(!in_nodes[i]){
            dfs(i);
        }
    }
    if(topology.size() == 0){
        cout << 0 << '\n';
        return 0;
    }
    reverse(topology.begin(), topology.end());

    int ans = 1;
    for(int i=0;i<topology.size()-1;i++){
        if(!is_edge(topology[i+1], topology[i])) ans = 2;
    }
    cout << ans << '\n';
    for(auto x : topology) cout << x << ' ';
    if(ans == 2){
        cout << '\n';
        for(int i=0;i<topology.size()-1;i++){
            if(!is_edge(topology[i+1], topology[i])){
                cout << topology[i+1] << ' ' << topology[i] << ' ';
                i++;
            }else{
                cout << topology[i] << ' ';
            }
        }
        cout << topology[topology.size()-1];
    }

}