#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
class Graph {
private:
//Variabile private
static int time;
int vertices;
int edges;
bool oriented;
vector<int> *adjacency_list;
//Functii private
void BFS(int starting_vertex, int *distances);
void DFS(int vertex,int* visited);
void BCC(int vertex, int* timer, int* lowest_reachable, int* visited, int* isArticulationPoint, int* parent, stack<int>& vertices_stack,vector<vector<int>>& components);
public:
Graph(int vertices = 0, int edges = 0, bool oriented = false);
~Graph();
void infoarena_graph();
void show_my_graph();
void solve_distances(int starting_vertex);
void solve_connected_components();
void solve_biconnected();
};
int main() {
int N,M;
fin>>N>>M;
Graph g(N,M, false);
g.infoarena_graph();
g.solve_biconnected();
}
#pragma region Initialization
Graph::Graph(int vertices, int edges, bool oriented) : vertices(vertices), edges(edges), oriented(oriented) {
adjacency_list = new vector<int>[vertices + 1];
}
Graph::~Graph() {
delete[] adjacency_list;
}
void Graph::infoarena_graph() {
int x, y;
if (oriented) {
for (int i = 1; i <= edges; i++) {
fin >> x >> y;
adjacency_list[x].push_back(y);
}
} else {
for (int i = 1; i <= edges; i++) {
fin>>x>>y;
adjacency_list[x].push_back(y);
adjacency_list[y].push_back(x);
}
}
}
void Graph::show_my_graph() {
for(int i = 1;i<vertices+1;i++){
cout<<i<<"=>";
for(int j : adjacency_list[i]){
cout<<j<<' ';
}
cout<<'\n';
}
}
#pragma endregion
int Graph::time = 0;
//Algorithm implementations
#pragma region Algorithms
void Graph::BFS(int starting_vertex, int *distances) {
int* visited = (int*) calloc(vertices+1,sizeof (int));
queue<int> que;
que.push(starting_vertex);
distances[starting_vertex] = 1;
visited[starting_vertex] = 1;
while (!que.empty()) {
int current_node = que.front();
que.pop();
for (auto neighbor : adjacency_list[current_node]) {
if (!visited[neighbor]) {
que.push(neighbor);
visited[neighbor] = 1;
distances[neighbor] = distances[current_node] + 1;
}
}
}
free(visited);
}
void Graph::DFS(int vertex, int *visited) {
visited[vertex] = 1;
for(auto neighbor : adjacency_list[vertex])
if(!visited[neighbor])
DFS(neighbor,visited);
}
void BCC_Helper(int vertex,vector<vector<int>> & components, stack<int>& vertices_stack,int* isArticulationPoint){
isArticulationPoint[vertex] = 1;
components.push_back(vector<int>());
int n = components.size();
while(vertices_stack.top()!=vertex){
components[n-1].push_back(vertices_stack.top());
cout<<vertices_stack.top()<<' ';
vertices_stack.pop();
}
components[n-1].push_back(vertices_stack.top());
cout<<vertices_stack.top();
cout<<"\n";
}
void Graph::BCC(int vertex, int* timer, int* lowest_reachable, int* visited, int* isArticulationPoint, int* parent, stack<int>& vertices_stack,vector<vector<int>>& components){
int children = 0;
vertices_stack.push(vertex);
visited[vertex] = 1;
timer[vertex] = time;
lowest_reachable[vertex] = time;
time+=1;
for(auto neighbor : adjacency_list[vertex]){
if(!visited[neighbor]){
children+=1;
parent[neighbor] = vertex;
if(children>1){
vertices_stack.push(vertex);
}
BCC(neighbor, timer, lowest_reachable, visited, isArticulationPoint, parent, vertices_stack, components);
lowest_reachable[vertex] = min(lowest_reachable[vertex],lowest_reachable[neighbor]);
if(parent[vertex] != 0 && lowest_reachable[neighbor] >= timer[vertex])
BCC_Helper(vertex,components,vertices_stack,isArticulationPoint);
}
else if (neighbor!=parent[vertex])
lowest_reachable[vertex] = min(lowest_reachable[vertex],timer[neighbor]);
}
if(parent[vertex] == 0 && children > 1){
BCC_Helper(vertex,components,vertices_stack,isArticulationPoint);
vertices_stack.pop();
}
}
#pragma endregion
//infoarena solutions
#pragma region Solutions
//Minimal distances BFS problem
void Graph::solve_distances(int starting_vertex) {
int *distances = (int*)calloc(vertices+1,sizeof (int));
BFS(starting_vertex,distances);
for(int i = 1;i<vertices+1;i++)
fout<<distances[i] - 1<<' ';
free(distances);
}
//Connected compontents DFS problem
void Graph::solve_connected_components() {
int counter = 0;
int* visited = (int*)calloc(vertices+1,sizeof (int));
for(int i = 1;i<vertices + 1;i++)
if(!visited[i]){
DFS(i,visited);
counter++;
}
fout<<counter;
free(visited);
}
void Graph::solve_biconnected() {
int* timer = (int*)calloc(vertices+1,sizeof(int));
int* lowest_reachable = (int*)calloc(vertices+1,sizeof(int));
int* visited = (int*)calloc(vertices+1,sizeof(int));
int* isArticulationPoint = (int*)calloc(vertices+1,sizeof(int));
int* parent = (int*)calloc(vertices+1,sizeof(int));
vector<vector<int>> components;
stack<int> vertices_stack;
for(int i = 1;i<vertices+1;i++){
if(!visited[i]){
BCC(i,timer,lowest_reachable,visited,isArticulationPoint,parent,vertices_stack,components);
}
}
if(!vertices_stack.empty()){
components.push_back(vector<int>());
while(!vertices_stack.empty()){
components[components.size()-1].push_back(vertices_stack.top());
vertices_stack.pop();
}
}
fout<<components.size()<<'\n';
for(int i = 0;i<components.size();i++){
for(int j : components[i]){
fout<<j<<' ';
}
fout<<'\n';
}
free(timer);
free(lowest_reachable);
free(visited);
free(isArticulationPoint);
free(parent);
}
#pragma endregion