#include <iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

int bejovo[200001] = {};
vector<int> megoldas1, megoldas2;
vector<vector<int>> adj;
int visited[200001] = {};
int returned[200001] = {};
bool valid = true;

void DFS_validity(int node)
{
    if(!valid){
        return;
    }
    if(visited[node] && !returned[node]){
        valid = false;
        return;
    }
    if(returned[node]){
        return;
    }
    visited[node] = true;
    for(int i = 0; i < adj[node].size(); i++){
        DFS_validity(adj[node][i]);
    }

    returned[node] = true;
    return;
}

void DFS1(int node)
{
    if(returned[node]){
        return;
    }
    for(int i = 0; i < adj[node].size(); i++){
        DFS1(adj[node][i]);
    }

    returned[node] = true;
    megoldas1.push_back(node);
}

void DFS2(int node)
{
    if(returned[node]){
        return;
    }
    for(int i = adj[node].size()-1; i >= 0; i--){
        DFS2(adj[node][i]);
    }

    returned[node] = true;
    megoldas2.push_back(node);
}

int main()
{
    int N, K;
    cin >> N >> K;
    adj.resize(N+1);


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

    for(int i = 1; i <= N; i++){
        if(!returned[i]){
            DFS_validity(i);
        }
    }

    if(!valid){
        cout << 0 << endl;
        return 0;
    }

    for(int i = 1; i <= N; i++){
        returned[i] = false;
    }
    for(int i = 1; i <= N; i++){
        if(!returned[i]){
            DFS1(i);
        }
    }
    for(int i = 1; i <= N; i++){
        returned[i] = false;
    }
    for(int i = N; i >= 1; i--){
        if(!returned[i]){
            DFS2(i);
        }
    }

    bool van_tobb_megoldas = false;
    for(int i = 0; i < N; i++){
        if(megoldas1[i] != megoldas2[i]){
            van_tobb_megoldas = true;
        }
    }

    if(van_tobb_megoldas){
        cout << 2 << endl;
        for(int i = N-1; i >= 0; i--){
            cout << megoldas1[i] << " ";
        }
        cout << endl;
        for(int i = N-1; i >= 0; i--){
            cout << megoldas2[i] << " ";
        }
    }
    else{
        cout << 1 << endl;
        for(int i = N-1; i >= 0; i--){
            cout << megoldas1[i] << " ";
        }
    }
    return 0;
}