#include <stdio.h>
#include <stdlib.h>



enum Colour{White,Gray,Black};
typedef struct Node{
    int key;
    Colour colour;
    int discovery_time,finish_time;
    Node *parent;

    int index;
    int comp;
    int low_link;
    bool onStack;

    int adjListSize;
    Node **adjList;
};
typedef struct Graph{
    int graph_size;
    Node **vertices;
};

int time=0,numCC=0,cnt=0,index=0,numSCC=0,stack_end=0;
int Minimum(int a,int b){
    return (a<b) ? a:b;
}
void DestroyGraph(Graph *graph){
    for(int i=0;i<graph->graph_size;i++){

        free(graph->vertices[i]->parent);
        graph->vertices[i]->parent=NULL;

        free(graph->vertices[i]->adjList);
        graph->vertices[i]->adjList=NULL;

        graph->vertices[i];
        free(graph->vertices[i]);
        graph->vertices[i]=NULL;
    }

    free(graph->vertices);
    graph->vertices=NULL;
}
void DFS_VISIT(Node *current_node,int space,Node **topSortNodes){

    for(int i=0;i<space;i++)
        printf("  ");
    printf("%d\n",current_node->key);

    time+=1;
    current_node->colour=Gray;
    current_node->discovery_time=time;
    for(int i=0;i<current_node->adjListSize;i++)
        if(current_node->adjList[i]->colour==White) {
            DFS_VISIT(current_node->adjList[i],space+1,topSortNodes);
        }

    current_node->colour=Black;
    time+=1;
    current_node->finish_time=time;

    if(NULL!=topSortNodes)
        topSortNodes[--cnt]=current_node;
}
void DFS(Graph *graph,Node **topSortNodes){

    for(int i=0;i<graph->graph_size;i++){
        graph->vertices[i]->colour=White;
        graph->vertices[i]->discovery_time=0;
        graph->vertices[i]->finish_time=0;
        graph->vertices[i]->parent=NULL;
    }

    time=0;
    numCC=0;
    cnt=graph->graph_size;
    for(int i=0;i<graph->graph_size;i++)
        if(graph->vertices[i]->colour==White) {
            DFS_VISIT(graph->vertices[i],0,topSortNodes);
            numCC++;
        }

}
void TopologicalSort(Graph *graph){

    Node **topSortNodes=(Node **) malloc(sizeof(Node *)*graph->graph_size);

    DFS(graph,topSortNodes);
    printf("Array of sorted nodes using topological sort:");
    for(int i=0;i<graph->graph_size;i++)
        printf("%d ",topSortNodes[i]->key);
    printf("\n");

    free(topSortNodes);
}
void StrongConnect(Node *current_node,Node **Stack,Node ***SCC,int *SCCsize){
  current_node->index=index;
  current_node->low_link=index;
  index+=1;

  Stack[stack_end++]=current_node;
  current_node->onStack= true;

  for(int i=0;i<current_node->adjListSize;i++) {
      if (current_node->adjList[i]->index == -1) {
          StrongConnect(current_node->adjList[i], Stack,SCC,SCCsize);
          current_node->low_link = Minimum(current_node->low_link, current_node->adjList[i]->low_link);
      } else if (current_node->adjList[i]->onStack)
          current_node->low_link = Minimum(current_node->low_link, current_node->adjList[i]->index);
  }

  if(current_node->low_link==current_node->index){
      int cnt=0;
      numSCC+=1;
      while(stack_end>0 && current_node!=Stack[stack_end-1]){
              SCC[numSCC-1][cnt++]=Stack[stack_end-1];
              Stack[stack_end - 1]->onStack = false;
              Stack[stack_end - 1]->comp = numSCC;
              stack_end--;
      }

      if(current_node==Stack[stack_end-1]){
          SCC[numSCC-1][cnt++]=Stack[stack_end-1];
          Stack[stack_end - 1]->onStack = false;
          Stack[stack_end - 1]->comp = numSCC;
          stack_end--;
      }
      SCC[numSCC-1]=(Node **) realloc(SCC[numSCC-1],cnt* sizeof(Node *));
      SCCsize[numSCC-1]=cnt;
  }
}
void Tarjan(Graph *graph){
    index=0;
    Node **Stack=(Node **) malloc(sizeof(Node *)*graph->graph_size);
    Node ***SCC=(Node ***) malloc(sizeof(Node **)*graph->graph_size);
    int *SCCsize=(int *) malloc(sizeof(int)*graph->graph_size);

    for(int i=0;i<graph->graph_size;i++)
        SCC[i]=(Node **) malloc(sizeof(Node *)*graph->graph_size);

    numSCC=0;
    stack_end=0;

    for(int i=0;i<graph->graph_size;i++){
        graph->vertices[i]->index=-1;
        graph->vertices[i]->onStack=false;
        graph->vertices[i]->comp=0;
        graph->vertices[i]->low_link=-1;
    }

    for(int i=0;i<graph->graph_size;i++)
        if(graph->vertices[i]->index==-1){
            StrongConnect(graph->vertices[i],Stack,SCC,SCCsize);
        }

//    printf("Number of Strongly connected components:%d",numSCC);
    printf("%d\n",numSCC);
    SCC=(Node ***) realloc(SCC,numSCC* sizeof(Node**));
    for(int i=0;i<numSCC;i++){
        for(int j=0;j<SCCsize[i];j++)
            printf("%d ",SCC[i][j]->key);
        printf("\n");
    }

    for(int i=0;i<numSCC;i++)
        free(SCC[i]);

    free(SCC);
    free(SCCsize);
    free(Stack);
}
void Undirected(){
    Graph graph;
    int n,m,x,y;
    scanf("%d",&n);
    scanf("%d",&m);

    graph.graph_size=n;
    graph.vertices=(Node **) malloc(sizeof(Node *)*n);
    for(int i=0;i<graph.graph_size;i++) {
        graph.vertices[i] = (Node *) malloc(sizeof(Node));
        graph.vertices[i]->adjListSize=0;
        graph.vertices[i]->key=i+1;
        graph.vertices[i]->adjList=(Node **) malloc(sizeof(Node *));
    }

    for(int i=0;i<m;i++){
        scanf("%d",&x);
        scanf("%d",&y);

        graph.vertices[x-1]->adjList=(Node **) realloc(graph.vertices[x-1]->adjList, sizeof(Node *)*(graph.vertices[x-1]->adjListSize+1));
        graph.vertices[y-1]->adjList=(Node **) realloc(graph.vertices[y-1]->adjList, sizeof(Node *)*(graph.vertices[y-1]->adjListSize+1));

        graph.vertices[x-1]->adjList[graph.vertices[x-1]->adjListSize++]=graph.vertices[y-1];
        graph.vertices[y-1]->adjList[graph.vertices[y-1]->adjListSize++]=graph.vertices[x-1];
    }

    DFS(&graph,NULL);
    printf("%d",numCC);
    DestroyGraph(&graph);
}
void DemoDFS(){

    printf("---DEMO DFS---\n");
    Graph graph;
    int n=5,m=5,x,y;


    graph.graph_size=n;
    graph.vertices=(Node **) malloc(sizeof(Node *)*n);
    for(int i=0;i<graph.graph_size;i++) {
        graph.vertices[i] = (Node *) malloc(sizeof(Node));
        graph.vertices[i]->adjListSize=0;
        graph.vertices[i]->key=i+1;
        graph.vertices[i]->adjList=(Node **) malloc(sizeof(Node *));
    }

    int arr1[5]={1,2,2,4,5};
    int arr2[5]={2,3,4,5,3};

    for(int i=0;i<m;i++){
        graph.vertices[arr1[i]-1]->adjList=(Node **) realloc(graph.vertices[arr1[i]-1]->adjList, sizeof(Node *)*(graph.vertices[arr1[i]-1]->adjListSize+1));
        graph.vertices[arr1[i]-1]->adjList[graph.vertices[arr1[i]-1]->adjListSize++]=graph.vertices[arr2[i]-1];
    }

    printf("Graph\n");
    for(int i=0;i<graph.graph_size;i++){
        printf("%d adjacency list:",graph.vertices[i]->key);
        for(int j=0;j<graph.vertices[i]->adjListSize;j++)
            printf("%d ",graph.vertices[i]->adjList[j]->key);

        printf("\n");
    }

    printf("DFS Tree:\n");
    DFS(&graph,NULL);
    DestroyGraph(&graph);
}
void DemoTopSort(){

    printf("---DEMO TOPOLOGICAL SORT---\n");
    Graph graph;
    int n=9,m=8,x,y;


    graph.graph_size=n;
    graph.vertices=(Node **) malloc(sizeof(Node *)*n);
    for(int i=0;i<graph.graph_size;i++) {
        graph.vertices[i] = (Node *) malloc(sizeof(Node));
        graph.vertices[i]->adjListSize=0;
        graph.vertices[i]->key=i+1;
        graph.vertices[i]->adjList=(Node **) malloc(sizeof(Node *));
    }

    int arr1[8]={1,1,3,3,5,4,4,4};
    int arr2[8]={2,3,4,5,9,6,7,8};

    for(int i=0;i<m;i++){
        graph.vertices[arr1[i]-1]->adjList=(Node **) realloc(graph.vertices[arr1[i]-1]->adjList, sizeof(Node *)*(graph.vertices[arr1[i]-1]->adjListSize+1));
        graph.vertices[arr1[i]-1]->adjList[graph.vertices[arr1[i]-1]->adjListSize++]=graph.vertices[arr2[i]-1];
    }

    printf("Graph\n");
    for(int i=0;i<graph.graph_size;i++){
        printf("%d adjacency list:",graph.vertices[i]->key);
        for(int j=0;j<graph.vertices[i]->adjListSize;j++)
            printf("%d ",graph.vertices[i]->adjList[j]->key);

        printf("\n");
    }

    printf("DFS Tree:\n");
    TopologicalSort(&graph);
    DestroyGraph(&graph);

}
void Directed(){
    Graph graph;
    int n,m,x,y;
    scanf("%d",&n);
    scanf("%d",&m);

    graph.graph_size=n;
    graph.vertices=(Node **) malloc(sizeof(Node *)*n);
    for(int i=0;i<graph.graph_size;i++) {
        graph.vertices[i] = (Node *) malloc(sizeof(Node));
        graph.vertices[i]->adjListSize=0;
        graph.vertices[i]->key=i+1;
        graph.vertices[i]->adjList=(Node **) malloc(sizeof(Node *));
    }

    for(int i=0;i<m;i++){
        scanf("%d",&x);
        scanf("%d",&y);
        graph.vertices[x-1]->adjList=(Node **) realloc(graph.vertices[x-1]->adjList, sizeof(Node *)*(graph.vertices[x-1]->adjListSize+1));
        graph.vertices[x-1]->adjList[graph.vertices[x-1]->adjListSize++]=graph.vertices[y-1];
    }

    TopologicalSort(&graph);
    DestroyGraph(&graph);
}
void DemoTarjan(){
    printf("---DEMO TARJAN SCC---\n");
    Graph graph;
    int n=8,m=12,x,y;

    graph.graph_size=n;
    graph.vertices=(Node **) malloc(sizeof(Node *)*n);
    for(int i=0;i<graph.graph_size;i++) {
        graph.vertices[i] = (Node *) malloc(sizeof(Node));
        graph.vertices[i]->adjListSize=0;
        graph.vertices[i]->key=i+1;
        graph.vertices[i]->adjList=(Node **) malloc(sizeof(Node *));
        graph.vertices[i]->low_link=0;
        graph.vertices[i]->index=0;
        graph.vertices[i]->onStack=false;
    }

    int arr1[12]={1,2,6,7,3,3,2,4,5,6,5,8};
    int arr2[12]={2,6,7,6,1,4,3,5,4,5,8,7};

    for(int i=0;i<m;i++){
        graph.vertices[arr1[i]-1]->adjList=(Node **) realloc(graph.vertices[arr1[i]-1]->adjList, sizeof(Node *)*(graph.vertices[arr1[i]-1]->adjListSize+1));
        graph.vertices[arr1[i]-1]->adjList[graph.vertices[arr1[i]-1]->adjListSize++]=graph.vertices[arr2[i]-1];
    }

    printf("Graph\n");
    for(int i=0;i<graph.graph_size;i++){
        printf("%d adjacency list:",graph.vertices[i]->key);
        for(int j=0;j<graph.vertices[i]->adjListSize;j++)
            printf("%d ",graph.vertices[i]->adjList[j]->key);

        printf("\n");
    }

    Tarjan(&graph);
    DestroyGraph(&graph);
}
void SolveSCC(){

        Graph graph;
        int n,m,x,y;
        scanf("%d",&n);
        scanf("%d",&m);

        graph.graph_size=n;
        graph.vertices=(Node **) malloc(sizeof(Node *)*n);
        for(int i=0;i<graph.graph_size;i++) {
            graph.vertices[i] = (Node *) malloc(sizeof(Node));
            graph.vertices[i]->adjListSize=0;
            graph.vertices[i]->key=i+1;
            graph.vertices[i]->adjList=(Node **) malloc(sizeof(Node *));
        }

        for(int i=0;i<m;i++){
            scanf("%d",&x);
            scanf("%d",&y);
            graph.vertices[x-1]->adjList=(Node **) realloc(graph.vertices[x-1]->adjList, sizeof(Node *)*(graph.vertices[x-1]->adjListSize+1));
            graph.vertices[x-1]->adjList[graph.vertices[x-1]->adjListSize++]=graph.vertices[y-1];
        }

        Tarjan(&graph);

    DestroyGraph(&graph);
}
int main() {

//    freopen("dfs.in","r",stdin);
//    freopen("dfs.out","w",stdout);
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
//    Undirected();
//    DemoDFS();
//    DemoTopSort();
//    DemoTarjan();
//   Directed();
    SolveSCC();

    return 0;
}