// UUID: e01bb8f3-ce7d-4592-bdf6-abd00feea34a
#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> topology;
vector<bool> vis;   
vector<vector<int>> adj;
vector<vector<bool>> is_edge;
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;
            exit(0);
        }else{
        }
    }
    //cout << "elhagy: " << v << '\n';
    active[v] = false;
    topology.push_back(v);
}

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>());
    is_edge.resize(n+1, vector<bool>(n+1, false));
    for(int i=1;i<=k;i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        is_edge[a][b] = true;
        is_edge[b][a] = true;
        in_nodes[b]++;
    }
    for(int i=1;i<=n;i++){
        if(!in_nodes[i]){
            dfs(i);
        }
    }
    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];
    }

}