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