#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;
}