/*
====================================================
##################  Code Author  ##################
====================================================
Md. Tahmid Hasan
#tahmidhasan3003
====================================================
Code Title: Finding Block in a Graph.cpp
====================================================
##############  Algorithm Reference  ##############
====================================================
Book Title: Introduction to Graph Theory (2nd ed.)
Author: Douglas B. West
ISBN: 978-81-7758-741-8
====================================================
4.1.23.* Algorithm. (Computing the blocks of a graph)
Input: A connected graph G. (The blocks of a graph are the blocks of its components, which can be found by depth-first search, so we may assume that G is connected.)
Idea: Build a depth-first search tree T of G, discarding portions of T as blocks are identified. Maintain one vertex called ACTIVE.
Initialization: Pick a root x ∈ V(H); make x ACTIVE; set T = {x}.
Iteration: Let v denote the current active vertex.
1) If v has an unexplored incident edge vw, then
	1A) If w ∉ V(T), then add vw to T, mark vw explored, make w ACTIVE.
	1B) If W ∈ V(T), then w is an ancestor of v; mark vw explored.
2) If v has no more unexplored incident edges, then
	2A) If v ≠ x, and w is the parent of v, make w ACTIVE. If no vertex in the current subtree T' rooted at v has an explored edge to an ancestor above w, then V(T') ∪ {w} is the vertex set of a block, record this information and delete V(T') from T.
	2B) If v = x, terminate.
====================================================
################  Important Notice  ################
====================================================
Input Details:-
1st line: total number of vertex (V)
2nd line: total number of edges (E)
Next E lines: vertex of edges (u v)
Last line: start vertex (root)
(Here is given a sample)
====================================================
filename: input.txt
(Put this .txt file in the same directory of source code. Content is given below.)
====================================================
11
13
0 1
0 3
0 4
0 8
0 10
1 2
2 3
4 5
4 7
4 10
5 6
6 7
9 10
10
====================================================
##################  Coding Start  ##################
====================================================
*/

#include<bits/stdc++.h>

using namespace std;

bool findConnection(int *adjMatrix, int *parentArray, int totalV, int node, int parent)   //search connection to ancestor
{
    int ancestor = parentArray[parent];
    while(ancestor != -1)
    {
        if(adjMatrix[ancestor*totalV+node] == 2)    //2 means explored edge
            return true;
        ancestor = parentArray[ancestor];
    }
    return false;
}

bool findBlock(int *adjMatrix, int *parentArray, int totalV, int root, int parent, stack<int>* blockPoints)
{
    if(findConnection(adjMatrix, parentArray, totalV, root, parent))    //find connection to ancestor
        return true;

    for(int i=0; i<totalV; i++)      //find vertex in tree of root
        if(parentArray[i] == root)   //child found of root
            if(findBlock(adjMatrix, parentArray, totalV, i, parent, blockPoints))   //call for child i
                return true;

    (*blockPoints).push(root);  //consider as block point
    parentArray[root] = -1;     //parent -1 means not parent means delete from tree
    return false;
}

int main()
{
    freopen("input.txt","r",stdin);
    int totalV, totalE, totalBlocks=0, rootX, activeV, associateW, tempU, tempV, *adjMatrix, *parentArray, *cutVertexArray;
    bool hasUnexploredE, isElement;
    stack <int> blockPoints;

    cin>>totalV>>totalE;    //total no of vertex and edges

    adjMatrix = (int*)malloc(sizeof(int)*totalV*totalV);    //creating adjacent matrix
    parentArray = (int*)malloc(sizeof(int)*totalV);         //creating parent container
    cutVertexArray = (int*)malloc(sizeof(int)*totalV);      //creating cut vertex container

    memset(adjMatrix, 0, sizeof(int)*totalV*totalV);        //set all value to 0
    memset(parentArray, -1, sizeof(int)*totalV);            //set all value to -1
    memset(cutVertexArray, 0, sizeof(int)*totalV);         //set all value to 0

    for(int i=0; i<totalE; i++)
    {
        cin>>tempU>>tempV;          //input space separated u,v vertex of an edge
        adjMatrix[tempU*totalV+tempV] = adjMatrix[tempV*totalV+tempU] = 1;
    }

    cin>>rootX;                 //root vertex
    activeV = rootX;            //set active
    parentArray[rootX] = -1;    //no parent

    while(1)
    {
        hasUnexploredE = false;
        for(int i=0; i<totalV; i++)             //unexplored edges checking
        {
            if(*(adjMatrix+activeV*totalV+i) == 1)
            {
                hasUnexploredE = true;
                associateW = i;
                break;
            }
        }
        if(hasUnexploredE)  //condition 1
        {
            isElement = false;

            if((associateW == rootX) || (parentArray[associateW] != -1))
                isElement = true;

            if(!isElement)  //Condition 1A
            {
                parentArray[associateW] = activeV;          //set a parent means added to tree
                adjMatrix[activeV*totalV+associateW] = adjMatrix[associateW*totalV+activeV] = 2;   //mark explored
                activeV = associateW;                       //change active vertex
            }
            else            //condition 1B
                adjMatrix[activeV*totalV+associateW] = adjMatrix[associateW*totalV+activeV] = 2; //mark explored
        }
        else        //condition 2
        {
            if(activeV != rootX)    //condition 2A
            {
                associateW = parentArray[activeV];  //pick parent of activeV
                if(!findBlock(adjMatrix, parentArray, totalV, activeV, associateW, &blockPoints))  //no vertex has explored edge to ancestor
                {
                    totalBlocks++;
                    cutVertexArray[associateW] = 1;
                    cout<<"Block "<<totalBlocks<<": "<<associateW<<" ";   //show block points
                    while(!blockPoints.empty())
                    {
                        cout<<blockPoints.top()<<" ";
                        blockPoints.pop();
                    }
                    cout<<endl;
                }
                activeV = associateW;               //make parent active
            }
            else    //condition 2B
                break;
        }
    }
    cout<<endl<<"Total Blocks: "<<totalBlocks<<endl;    //total blocks
    cout<<"Articulation Points: ";                      //cut vertex
    for(int i=0; i<totalV; i++)
        if(cutVertexArray[i])
            cout<<i<<" ";
    cout<<endl;

    return 0;
}