/// Algoritmul lui Kosaraju ( https://en.wikipedia.org/wiki/Kosaraju's_algorithm#Complexity )
/// Complexitate: O(n+m) ( face doar 3 (2+1) traversari ale grafului ( unul pentru graful normal, unul pentru trnasversal si inca unul pentru a determina si numarul ctc inainte de printarea lor)
#include <iostream>
#include <stack>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
int k;
class Graf
{
private:
    int N;
    vector<int> *adiacenta;
    void dfs(int v, int vizitat[] );
    void dfs_fara_printare(int v, int vizitat[] );
    void OrderFilling (stack<int> &stiva, int n, int vizitat[]);

public:
    Graf(int n);

    Graf Transpus();

    void adaugare_muchie(int x, int y);
    void ctc();
    vector<int>* getter_vector()
    {
        return adiacenta;
    }
};

Graf::Graf(int n)
{
    this->N=n+1;
    adiacenta= new vector<int>[n+1];
}

void Graf::dfs(int n, int vizitat[])   /// dfs normal cu recurenta
{
    vizitat[n] = 1;
    if (n!=0)
        g<<n<<" ";

    for(int i= 0; i < adiacenta[n].size(); i++)
    {
        int urm = adiacenta[n][i];
        if(!vizitat[urm])
            dfs(urm,vizitat);
    }
}


void Graf::dfs_fara_printare(int n, int vizitat[])    /// dfs care imi trebuia pentru a afisa numarul lor inainte de a afisa nodurile din ele
{
    vizitat[n] = 1;
    for(int i= 0; i < adiacenta[n].size(); i++)
    {
        int urm = adiacenta[n][i];
        if(!vizitat[urm])
            dfs_fara_printare(urm,vizitat);
    }
}


Graf Graf::Transpus()   /// trebuie facut transpusul pentru a acoperi metoda plus-minus descrisa la indicatii
{
    Graf g(N);
    // cout<<"Test"<<endl;
    for (int v = 0; v < N; v++)
    {

        /// efectiv transpunerea grafului initial
        vector<int>::iterator i;
        for(i = adiacenta[v].begin(); i != adiacenta[v].end(); ++i)
        {
            g.adiacenta[*i].push_back(v);
        }

    }

    return g;
}

void Graf::adaugare_muchie(int x, int y)
{
    adiacenta[x].push_back(y);
    //cout<<"Test"<<endl;
}

void Graf::OrderFilling (stack<int> &stiva, int n, int vizitat[])   /// algoritmul isi alege punctele de plecare pentru dfs in functie de viteza de terminare a dfs ului pentru fiecare nod, aceste puncte le introduce intr-o stiva
{
    // cout<<"Test"<<endl;
    vizitat[n]= 1;
    for(int i= 0; i < adiacenta[n].size(); i++)
    {
        int urm = adiacenta[n][i];
        if(!vizitat[urm])
            OrderFilling(stiva,urm,vizitat);
    }

    stiva.push(n);
}

void Graf::ctc()
{
    stack<int> stiva;
    int *vizitat = new int[N];

    for(int i = 0; i < N; i++)
        vizitat[i] = 0;
    //cout<<"test"<<endl;
    for(int i = 0; i < N; i++)
        if(vizitat[i] == 0)
            OrderFilling(stiva, i, vizitat);

    //cout<<"test"<<endl;
    Graf g1= Transpus();

    for (int i=0; i<N; i++)
        vizitat[i]=0;

    stack<int> copie_stiva = stiva;    /// copie la stiva pentru a returna numarul de componente inainte de a le afisa
    int* vizitat_copie = new int[N];
    for (int i=0; i<N; i++)
        vizitat_copie[i]=0;

    int k=0;
    while (stiva.empty() == false)
    {
        /// dupa fiecare dfs(x) calculat se scoate acel nod din stiva
        int x = stiva.top();
        stiva.pop();


        if (vizitat[x] == 0)
        {
            g1.dfs_fara_printare(x,vizitat);   /// daca raman nevizitate dupa fiecare dfs calculat inseamna ca am gasit o componenta si nodul ei de start
            k++;
        }

    }
    g<<k-1<<endl;

    int k1=0;
    while (copie_stiva.empty() == false)
    {
        int x = copie_stiva.top();
        copie_stiva.pop();
        vizitat_copie[0]=1;
        if (vizitat_copie[x] == 0)
        {
            g1.dfs(x,vizitat_copie);
            g << endl;
        }
    }
}

int main()
{
    int n,m,x,y;
    f>>n>>m;
    Graf g(n);
    for (int i=1;i<=m;i++)
    {
        f>>x>>y;
        g.adaugare_muchie(x, y);
        sort(g.getter_vector()->begin(), g.getter_vector()->end());
    }
    g.ctc();

    /*
    Graf g(8);
	g.adaugare_muchie(1, 2);
	g.adaugare_muchie(2, 6);
	g.adaugare_muchie(6, 7);
	g.adaugare_muchie(7, 6);
	g.adaugare_muchie(3, 1);
	g.adaugare_muchie(3, 4);
	g.adaugare_muchie(2, 3);
	g.adaugare_muchie(4, 5);
	g.adaugare_muchie(5, 4);
	g.adaugare_muchie(6, 5);
	g.adaugare_muchie(5, 8);
	g.adaugare_muchie(8, 7);


    for (int i=0;i<9;i++)
        sort(g.getter_vector()[i].begin(), g.getter_vector()[i].end());
	g.ctc();

	*/

    return 0;
}