#include <iostream>
#include <vector>
#include <deque>
#define ll long long
using namespace std;
struct element
{
bool seen,rseen;
ll in, out;
vector < ll> sz, rsz;
};
vector <element> x;
ll n, i, j, m, a, b;
deque <ll> res, rres;
bool ok2 = false;
void topo(ll curr)
{
x[curr].seen = true;
for (auto& e : x[curr].sz)
{
if (!x[e].seen)
{
topo(e);
}
}
res.push_front(curr);
}
void rtopo(ll curr)
{
x[curr].rseen = true;
for (auto& e : x[curr].rsz)
{
if (!x[e].rseen)
{
rtopo(e);
}
}
rres.push_back(curr);
}
int main()
{
cin >> n >> m;
x.resize(n + 1);
for (i = 1; i <= m; ++i)
{
cin >> a >> b;
x[a].sz.push_back(b);
x[b].rsz.push_back(a);
x[a].out++;
x[b].in++;
}
vector <ll> start, rstart;
for (i = 1; i <= n; ++i)
{
if (x[i].in == 0) start.push_back(i);
if (x[i].out == 0) rstart.push_back(i);
}
if (start.size() == 0)
{
cout << "0";
return 0;
}
if (start.size() == 1)
{
topo(start[0]);
if (res.size() != n)
{
cout << "0";
return 0;
}
rtopo(res.back());
if (res.size() == rres.size())
{
for (i = 0; i < n; ++i)
{
if (res[i] != rres[i]) break;
}
if (i == n)
{
cout << "1\n";
for (auto& e : res) cout << e << " ";
return 0;
}
}
for (i = 0; i < min(res.size(), rres.size()); ++i)
{
if (res[i] != rres[i]) break;
}
cout << "2\n";
for (auto& e : res) cout << e << " ";
cout << "\n";
for (auto& e : rres) cout << e << " ";
while (i<n && !x[res[i]].rseen)
{
cout << res[i] << " ";
++i;
}
return 0;
}
ok2 = true;
deque <ll> R;
//for (auto& e : start) R.push_back(e);
for (auto& e : start)
{
while (!res.empty())
{
res.pop_front();
if (!res.empty()) R.push_back(res[0]);
}
topo(e);
}
res.pop_front();
if (R.size() + res.size() + start.size() != n)
{
cout << "0";
return 0;
}
cout << "2\n";
for (auto& e : start) cout << e << " ";
for (auto& e : R) cout << e << " ";
for (auto& e : res) cout << e << " ";
cout << "\n";
cout << start.back() << " ";
start.pop_back();
for (auto& e : start) cout << e << " ";
for (auto& e : R) cout << e << " ";
for (auto& e : res) cout << e << " ";
return 0;
}
/*
5 4
3 2
2 1
1 5
1 4
*/