#include <iostream>
#include <fstream>
#include <list>
#include <queue>
#include <stack>
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

class grafuri_orientate
{
    unsigned int numar_noduri;
    list <int> *lista;
    list <int> *revlista;
    public:
    grafuri_orientate(unsigned int a=0) //Constructorul
        {
            numar_noduri=a;
            lista=new list<int> [a];
            revlista=new list <int> [a];
        };

    friend istream & operator >>( istream& i, grafuri_orientate & A);
    bool get_data_graf();
    bool parcurgere_in_latime(int nod,bool type);
    bool parcurgere_in_adancime(int nod);
    bool parcurgere(int nod,bool visited[], stack <int> &sol);
    bool dfs_reverse(int nod, bool *visited, list <int> *&a,int nr);
    bool componente_tare_conexe();
    bool get_matricea_drumurilor();
};

int main()
{
     //cout<<"Iti multumesc ca m-ai ales pe mine(acest program in codeblocks) pentru a te ajuta cu grafurile tale orientate";
      //  cout<<"\nDatele despre graf sunt introduse in fisierul date.in iar rezultatele pe care le furnizez eu(programul)\nsunt scrise in fisierul date.out\n";
    grafuri_orientate A;
    f>>A;
    /*int ok=0;
    do
    {
        cout<<"\n\nAlege una din procedurile mele introducand codul specific:\n\n1)Parcurgerea in latime: 1\n2)Parcurgere in adancime: 2\n3)Determinare componente tare conexe: 3\n4)Determinare matricii drumurilor: 4\n5)Oprirea executiei programului: 0\n";
        cin>>ok;
            if(ok==1)
            {
                cout<<"\n\nAi optat pentru parcurgerea in latime,\nte rog alege un nod din care doresti sa se porneasca parcurgerea: ";
                int nod;
                cin>>nod;
                A.parcurgere_in_latime(nod,true);g<<"\n\n";
                cout<<"\nParcurgerea a fost afisata in fisierul date.out\n";
            }
            else
            if(ok==2)
            {
                cout<<"\n\nAi optat pentru parcurgerea in adancime,\nte rog alege un nod din care doresti sa se porneasca parcurgerea: ";
                int nod;
                cin>>nod;
                g<<"Parcurgerea in adancime pornita din nodul "<<nod<<" trece prin nodurile: ";
                A.parcurgere_in_adancime(nod);  g<<"\n\n";
                cout<<"\nParcurgerea a fost afisata in fisierul date.out\n";
            }
            else
            if(ok==3)
            {
                g<<"Componentele tare conexe sunt:\n";
                A.componente_tare_conexe();g<<"\n";
                cout<<"\n\nComponentele tare conexe au fost afisate in fisierul date.out\n";
            }
            else
            if(ok==4)
            {
                g<<"Matricea drumurilor asociata grafului este:\n";
                A.get_matricea_drumurilor();g<<"\n";
                cout<<"\n\nMatricea drumurilor a fost afisata in fisierul date.out\n";
            }
            else
            if(ok!=0)
            {
                cout<<"\n\nCOdul introdus este nevalid(nerecunoscut de program), te rog introdu un alt cod.\n\n";
                ok=5;
            }

    }while(ok!=0);
    cout<<"\n\nIti multumesc ca m-ai ales pe mine(programul care tocmai a fost rulat) sa iti rezolv aceste cerinte pe graful orientat!!";
    */
    A.componente_tare_conexe();
    return 0;
}



std:: istream & operator >>(std:: istream & i,  grafuri_orientate & A)
{
    unsigned int m;
    i>>A.numar_noduri;
    i>>m;
    A.lista=new list <int> [A.numar_noduri+1];
    A.revlista=new list <int> [A.numar_noduri+1];
    for(unsigned int l=1;l<=m;l++)
    {
        int x,y;
        i>>x>>y;
        A.lista[x].push_back(y);
        A.revlista[y].push_back(x);
    }
    return i;
}

bool grafuri_orientate:: parcurgere_in_latime( int nod,bool type)
{
    if(type==true)g<<"Parcurgera in latime pornita din nodul "<<nod<<" trece prin nodurile: ";
    queue <int> coada;
    bool visited[numar_noduri+1];
    for(unsigned int i=0;i<=numar_noduri+1;i++) visited[i]=0;

    coada.push(nod);
    visited[nod]=1;
    while(!coada.empty())
    {
        int k=coada.front();
        if(type==true)
        g<<k<<" ";
        for(list <int>:: iterator it=lista[k].begin();it!=lista[k].end();it++)
        if(visited[*it]==0)
        {
            coada.push(*it);
            visited[*it]=1;
        }
        coada.pop();
    }
    if(type==false)
    {for(unsigned int i=1;i<=numar_noduri;++i)
    g<<visited[i]<<" ";
    g<<"\n";
    }
    return 1;
}
bool grafuri_orientate:: parcurgere(int nod,bool visited[],stack <int> &sol)
{
    visited[nod]=1;
    for(list <int> :: iterator it=lista[nod].begin();it!=lista[nod].end();++it)
    if(visited[*it]==0)
        {
            parcurgere(*it,visited,sol);
        }
   sol.push(nod);

    return 1;
}

bool grafuri_orientate:: parcurgere_in_adancime(int nod)
{
    bool visited[numar_noduri+1];
    stack <int> sol,solrev;
    for(unsigned int i=1;i<=numar_noduri;i++) visited[i]=0;
    for(unsigned int i=1;i<=numar_noduri;++i)
    if(visited[i]==0)
     {parcurgere(i,visited,sol);
     }
    while(!sol.empty())
    {
        g<<sol.top()<<" ";
        sol.pop();
    }
    return 1;
}


bool grafuri_orientate::get_data_graf()
{
    g<<"Graful are: "<<this->numar_noduri<<" noduri\n";
    for(unsigned int i=1;i<=this->numar_noduri;i++)
    {
        g<<"Nodul "<<i<<" are muchie catre nodurile: ";
        for(list <int> ::iterator it=this->lista[i].begin();it!=this->lista[i].end();it++)
        g<<*it<<" ";
        g<<"\n";
    }
    g<<"\n";
    g<<"Graful cu muchiile inversate:";
        for(unsigned int i=1;i<=this->numar_noduri;i++)
    {
        g<<"Nodul "<<i<<" are muchie catre nodurile: ";
        for(list <int> ::iterator it=this->revlista[i].begin();it!=this->revlista[i].end();it++)
        g<<*it<<" ";
        g<<"\n";
    }

    return 1;
}


bool grafuri_orientate::dfs_reverse(int nod, bool *visited, list <int> *&a,int nr)
{
    visited[nod]=0;
    for(list <int> :: iterator it=revlista[nod].begin();it!=revlista[nod].end();++it)
    if(visited[*it]==1)
    {
        dfs_reverse(*it,visited,a,nr);
    }
    a[nr].push_back(nod);
    return 1;
}

bool grafuri_orientate:: componente_tare_conexe()
{
    stack <int> sol;
    bool visited[numar_noduri+1];
    list <int> *solutii; solutii=new list <int> [numar_noduri+1];
    int nur=0;   //Numarul solutiilor
    for(unsigned int i=1;i<=numar_noduri;++i) visited[i]=0;

    for(unsigned int i=1;i<=numar_noduri;++i)
    if(visited[i]==0)
    parcurgere(i,visited,sol);
     while(!sol.empty())
         {if(visited[sol.top()]==1)
         {

             nur++;
            dfs_reverse(sol.top(),visited,solutii,nur);

         }
         sol.pop();
         }
     g<<nur<<"\n";
     for(int i=1;i<=nur;++i)
     {
         for(list <int> :: iterator it=solutii[i].begin();it!=solutii[i].end();++it)
         g<<*it<<" ";
         g<<"\n";
     }
     return 1;
}

bool grafuri_orientate:: get_matricea_drumurilor()
{
    for(unsigned int i=1;i<=numar_noduri;++i)
    parcurgere_in_latime(i,false);
    return true;
}