#include <bits/stdc++.h>

using namespace std;
/*
ez egy iranyitott graf
a feladat egy topologikus sorbarendezest talalni (ugy kell sorba rendezni a gyerekeket, hogy minden a<b parra a elobb szerepel, mint b
probaljunk meg egy ilyen sort talalni
ha valaki senkinel sem magasabb, az nyilvan kerulhet a sor elejere
ha utana van olyan aki a tobbi embernel nem magasabb az kerulhet a masodik helyre
es igy tovabb

ha nem sikerul mindenkinek helyet talalni, akkor van egy csoport, ahol mindenki magasabb valaki masnal, tehat nincs tornasor 0 a megoldas
egyebkent ez egy jo megoldas
ha barmely ket szomszedos emberre tudjuk, hogy a kesobb levo magasabb, akkor ez az egyetlen egy sorrend
mas esetben oket ki lehet cserelni, es az egy masik lehetseges tornasor
*/
const int c=200005;
int n, m, be[c], sor[c], cnt;
vector<int> sz[c];
queue<int> q;
int main()
{


    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    for (int i=1; i<=m; i++) {
        int a, b;
        cin >> a >> b;
        be[b]++;
        sz[a].push_back(b);
    }
    // be a csucs befoka (hagy nala alacsonyabb van, aki nincs a sorban)
    for (int i=1; i<=n; i++) {
        if (be[i]==0) {
            q.push(i);
            // ot is kerulhet a sor elejere
        }
    }
    while (q.size()>0) {
        int a=q.front();
        q.pop();
        cnt++;
        // a kapta a cnt. helyet
        sor[cnt]=a;
        for (auto x:sz[a]) {
            be[x]--;
            // uj emberek kerulhetnek a sor elejere
            if (!be[x]) {
                q.push(x);
            }
        }
    }

    if (cnt<n) {
        // nincs jo sorbarendezes
        cout << 0 << "\n";
        return 0;
    }
    int valt=0;
    for (int i=1; i<n; i++) {
        int a=sor[i], b=sor[i+1];
        bool csere=1;
        for (auto x:sz[a]) {
            if (x==b) {
                csere=0;
            }
        }
        if (csere) {
            // ki lehet cserelne az i. es i+1. embert a sorban
            valt=i;
        }
    }
    if (!valt) {
        // 1 megoldas
        cout << 1 << "\n";
        for (int i=1; i<=n; i++) {
            cout << sor[i] << " ";
        }
        cout << "\n";
    } else {
        // 2 megoldas
        cout << 2 << "\n";
        for (int i=1; i<=n; i++) {
            cout << sor[i] << " ";
        }
        cout << "\n";
        swap(sor[valt], sor[valt+1]);
        for (int i=1; i<=n; i++) {
            cout << sor[i] << " ";
        }
        cout << "\n";
    }
    return 0;
}