#include <bits/stdc++.h>
using namespace std;
int main()
{
    //ifstream f("szamok.txt");
    int n,m; cin>>n>>m;
    vector<int>a[n+1];
    vector<int>t(n+1);
    for(int i=0; i<m; i++){
        int x,y; cin>>x>>y;
        a[x].push_back(y); t[y]++;}
    int vand=-1;
    queue<int>q;
    for(int i=1; i<=n; i++){
        if(t[i]==0)q.push(i);}
    vector<int>ut;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        ut.push_back(x);
        if(!q.empty())vand=ut.size()-1;
        for(int i:a[x]){
            t[i]--;
            if(t[i]==0)q.push(i);}
        }
    if(ut.size()!=n)cout<<0<<endl;
    else if(vand==-1){
        cout<<1<<endl;
        for(int i:ut)cout<<i<<" ";
        }
    else {
        cout<<2<<endl;
        for(int i:ut)cout<<i<<" ";
        cout<<endl;
        for(int i=0; i<n; i++){
            if(i==vand)cout<<ut[i+1]<<" ";
            else if(i==vand+1)cout<<ut[i-1]<<" ";
            else cout<<ut[i]<<" ";}}
    return 0;
}