#include <iostream>
#include <fstream>
#include <set>
using namespace std;
ifstream fin("mesaj.in");

int A[100][100],x,postordine[100],viz[100],n,m,y,nr=0,nrm=0,vfs=0,vfMax=0,prag=0,AT[100][100];

//sortare topologica
void dfs (int x){
    
    
    viz[x]=1;
    //cout<<x<<" ";
    for(int i=1;i<=A[x][0];i++)
        if(viz[A[x][i]]==0){
            dfs(A[x][i]);
        }
    postordine[++nr]=x;
}
void dfst (int x, int root){
    
    
    viz[x]=0-root;
    cout<<x<<" ";
    for(int i=1;i<=AT[x][0];i++)
        if(viz[AT[x][i]]>0){
            dfst(AT[x][i],root);
        }
    
}
int main()
{
    fin>>n;
    fin>>m;
    for(int i=0;i<m;i++)
        {
            fin>>x>>y;
            A[x][0]++;
            A[x][A[x][0]]=y;
            AT[y][0]++;
            AT[y][A[y][0]]=x;
        }
    for(int i=1;i<=n;i++){
        if(!viz[i]){
            dfs(i);
        }
    }
    for(int i=n;i>0;i--)
        cout<<postordine[i]<<" ";

    for(int i=n;i>0;i--){
        if(viz[postordine[i]]>0){
            nrm++;
            dfst(postordine[i],nrm);
            cout<<'\n';
        }
    }
    for(int i=n;i>0;i--)
        cout<<viz[i]<<" ";
    cout<<'\n';
    cout<<nrm;
    return 0;
}