// UUID: e05fa0df-38b9-4b5c-b3ed-29bc0452878b
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k; cin >> n >> k;
    vector<vector<int>> g(n + 1);
    vector<int> beelek(n + 1, 0);
    vector<vector<int>> solutions(2);
    for (int i = 0; i < k; i++) {
        int a, b; cin >> a >> b;
        g[b].push_back(a);
        beelek[b]++;
    }
    beelek[0] = -1;
    while (!all_of(begin(beelek), end(beelek), [](int i) { return i < 0; })) {
        vector<int> forrasok;
        for (int i = 1; i <= n; i++) {
            if (beelek[i] == 0) {
                forrasok.push_back(i);
            }
        }
        if (forrasok.size() == 0) {
            cout << 0; return 0;
        }
        else {
            for (int i = 0; i < forrasok.size(); i++) {
                solutions[0].push_back(forrasok[i]);
                solutions[1].push_back(forrasok[forrasok.size() - 1 - i]);
            }
        }
        for (int j : forrasok) {
            beelek[j] = -1;
            for (int i : g[j]) {
                beelek[i]--;
            }
        }
        
    }
    int o = 1;
    for (int i = 0; i < n; i++) {
        if (solutions[0][i] != solutions[1][i]) {
            o = 2; break;
        }
    }
    cout << o << endl;
    for (int i : solutions[0]) {
        cout << i << " ";
    }
    cout << endl;
    if (o == 2) {
        for (int i : solutions[1]) {
            cout << i << " ";
        }
    }
}
// #include <bits/stdc++.h>
// #include <vector>
// #include <numeric>

// using namespace std;

// int main() {
//     ios::sync_with_stdio(false);
//     cin.tie(0);
//     int n, k; cin >> n >> k;
//     vector<vector<int>> g(n + 1);
//     vector<int> beelek(n + 1, 0);
//     vector<vector<int>> solutions(2);
//     for (int i = 0; i < k; i++) {
//         int a, b; cin >> a >> b;
//         g[a].push_back(b);
//         beelek[b]++;
//     }
//     beelek[0] = -1;
//     // sor letrehozas
//     queue<int> forrasok;
//     vector<int> sorrend;
//     // sorba bepakoljuk az osszes forrast
//     for (int i = 1; i <= n; i++) {
//         if (beelek[i] == 0) {
//             forrasok.push(i);
//         }
//     }
//     while (forrasok.size() != 0) {
//         // kiszedunk 1 forrast a sorbol
//         // toroljuk az ő éleit és a sorrend végére tesszük

//         int x = forrasok.front();
//         forrasok.pop();
//         sorrend.push_back(x);

//         for (int i : g[x]){
//             --beelek[i];
//             if(beelek[i] == 0) forrasok.push(i);
//         }
//     }

//     if (sorrend.size()<n){
//         cout<<0; return 0;
//     }
//     vector<int> sorrend2;
//     for(int i = 0 ; i < n - 1; i++){
//         if (find(g[sorrend[i]].begin(), g[sorrend[i]].end(), sorrend[i+1]) != g[sorrend[i]].end()){
//             // sorrend2 = 
//         }
//     }
//     // for(int i = 0; i < n; i++){
//     //     cout<<sorrend[i];
//     // }
// }


// /*


// beolvasasás
// befokok számolása

// sor létrehozása
// források a sorba

// queue <int> q;
// vector <int> ans;

// while (q.size()>0){
    
//     int x = q.front();
//     q.pop();

//     for (int y : g[x]) {
//         y befokát csökkentem
//         ha 0-ra csökkent, akkor beteszem a sorba
//     }

// }

// ans mérete alapján eldöntöm

// ----------------------------------------

// Létezik-e több?


// */