#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
class Graf{
public:
struct edge{
int from;
int to;
int cost;
};
Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList);
Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList, bool isCostGraph);
void test();
vector<int> bfs(int start);
int dfs();
vector<vector<int>> biconnectedComponents();
private:
//date membre
int m_nrNodes;
int m_nrEdges;
bool m_isOriented;
bool m_isCostGraph;
vector<vector<int>> m_adjacencyList;
vector<edge> m_edges;
//functii ajutatoare
void dfsRec(int start, vector<bool> &visited);
void biconnectedComponentsDFS(int u, vector<int> &disc, vector<int> &low, vector<edge> &st, vector<int> &parent, vector<vector<int>> &result);
};
Graf::Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList) {
m_nrNodes = nrNodes;
m_nrEdges = nrEdges;
m_isOriented = isOriented;
m_isCostGraph = false;
edge crtEdge;
m_adjacencyList.resize(nrNodes + 1);
for(int i = 1; i <= nrNodes; i++){
for(int j = 0; j < adjacencyList[i].size(); j++){
m_adjacencyList[i].push_back(adjacencyList[i][j]);
if(!isOriented){
m_adjacencyList[adjacencyList[i][j]].push_back(i);
}
crtEdge.from = i;
crtEdge.to = adjacencyList[i][j];
crtEdge.cost = 0;
m_edges.push_back(crtEdge);
}
}
}
void Graf::test(){
cout << m_nrNodes << " " << m_nrEdges << '\n';
for(int i = 1; i <= m_nrNodes; i++){
cout<<i<<": ";
for(int j : m_adjacencyList[i]){
cout<<j<<", ";
}
cout<<'\n';
}
}
Graf::Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList, bool isCostGraph) {
//cand ajungem la costuri
}
vector<int> Graf::bfs(int start) {
vector<int> result;
vector<bool> visited;
for(int i=1; i<=m_nrNodes+1; i++){
visited.push_back(false);
}
deque<int> dq;
vector<int> prev;
for(int i=1; i<=m_nrNodes+1; i++){
prev.push_back(0);
}
dq.push_back(start);
visited[start] = true;
while(!dq.empty()){
int crt = dq.front();
dq.pop_front();
for(int i : m_adjacencyList[crt]){
if(!visited[i]){
dq.push_back(i);
visited[i] = true;
prev[i] = crt;
}
}
}
for(int f = 1; f <= m_nrNodes; f++){
int steps = 0;
int lastVisited;
for(int i = f; i != 0; i = prev[i]){
steps++;
lastVisited = i;
}
if(lastVisited != start) { result.push_back(-1); }
else { result.push_back(steps - 1); }
}
return result;
}
int Graf::dfs() {//ar trebui mai degraba sa tina de dfs infoarena cred, dar vad eu
vector<bool> visited;
for(int i = 0; i <= m_nrNodes; i++){
visited.push_back(false);
}
int nrConexComponents = 0;
for(int i = 1; i <= m_nrNodes; i++){
if(!visited[i]){
nrConexComponents++;
dfsRec(i, visited);
}
}
return nrConexComponents;
}
void Graf::dfsRec(int start, vector<bool> &visited) {
visited[start] = true;
for(auto i : m_adjacencyList[start]){
if(!visited[i]){
dfsRec(i, visited);
}
}
}
vector<vector<int>> Graf::biconnectedComponents() {
vector<int> disc, low, parent;
vector<edge> st;
// Initialize disc and low, and parent arrays
for (int i = 0; i <= m_nrNodes; i++) {
disc.push_back(-1);
low.push_back(-1);
parent.push_back(-1);
}
vector<vector<int>> result;
for (int i = 1; i <= m_nrNodes; i++) {
if (disc[i] == -1)
biconnectedComponentsDFS(i, disc, low, st, parent, result);
vector<int> component;
int j = 0;
// If stack is not empty, pop all edges from stack
while (!st.empty()) {
j = 1;
bool isFrom = false, isTo = false;
for(int node : component){
if(node == st.back().to){
isTo = true;
}
if(node == st.back().from){
isFrom = true;
}
}
if(!isFrom && !isTo){
component.push_back(st.back().to);
}
else if(isFrom && !isTo){
component.push_back(st.back().to);
}
else if(!isFrom && isTo){
component.push_back(st.back().from);
}
st.pop_back();
}
if (j == 1) {
result.push_back(component);
}
}
return result;
}
void Graf::biconnectedComponentsDFS(int u, vector<int> &disc, vector<int> &low, vector<edge> &st, vector<int> &parent, vector<vector<int>> &result) {
static int time = 0;
// Initialize discovery time and low value
disc[u] = low[u] = ++time;
int children = 0;
// Go through all vertices adjacent to this
for (auto v : m_adjacencyList[u]) {
// If v is not visited yet, then recur for it
if (disc[v] == -1) {
children++;
parent[v] = u;
// store the edge in stack
edge crtEdge{u, v, 0};
st.push_back(crtEdge);
biconnectedComponentsDFS(v, disc, low, st, parent, result);
// Check if the subtree rooted with 'v' has a
// connection to one of the ancestors of 'u'
if(low[u] > low[v]) low[u] = low[v];
vector<int> component;
// If u is an articulation point,
// pop all edges from stack till u -- v
if ((disc[u] == 1 && children > 1) || (disc[u] > 1 && low[v] >= disc[u])) {
while (st.back().from != u || st.back().to != v) {
bool isFrom = false, isTo = false;
for(int node : component){
if(node == st.back().to){
isTo = true;
}
if(node == st.back().from){
isFrom = true;
}
}
if(!isFrom && !isTo){
component.push_back(st.back().to);
}
else if(isFrom && !isTo){
component.push_back(st.back().to);
}
else if(!isFrom && isTo){
component.push_back(st.back().from);
}
st.pop_back();
}
bool isFrom = false, isTo = false;
for(int node : component){
if(node == st.back().to){
isTo = true;
}
if(node == st.back().from){
isFrom = true;
}
}
if(!isFrom && !isTo){
component.push_back(st.back().to);
}
else if(isFrom && !isTo){
component.push_back(st.back().to);
}
else if(!isFrom && isTo){
component.push_back(st.back().from);
}
st.pop_back();
result.push_back(component);
}
}
else if (v != parent[u]) {
if(low[u] > low[v]) low[u] = low[v];
if (disc[v] < disc[u]) {
edge crtEdge{u, v, 0};
st.push_back(crtEdge);
}
}
}
}
void bfsInfoArena(){
ifstream fin("bfs.in");
ofstream fout("bfs.out");
int n, m, x, from, to;
vector<vector<int>> la;
fin>>n>>m>>x;
la.resize(n+1);
for(int i = 0; i < m; i++){
fin>>from>>to;
la[from].push_back(to);
}
Graf graf = Graf(n, m, true, la);
vector<int> res = graf.bfs(x);
for(int i : res){
fout<<i<<" ";
}
}
void dfsInfoArena(){
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n, m, from, to;
vector<vector<int>> la;
fin>>n>>m;
la.resize(n+1);
for(int i = 0; i < m; i++){
fin>>from>>to;
la[from].push_back(to);
}
Graf graf = Graf(n, m, false, la);
fout<<graf.dfs();
}
void biconexInfoArena(){
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, from, to;
vector<vector<int>> la;
fin>>n>>m;
la.resize(n+1);
for(int i = 0; i < m; i++){
fin>>from>>to;
la[from].push_back(to);
}
Graf graf = Graf(n, m, false, la);
vector<vector<int>> componenteBiconexe = graf.biconnectedComponents();
fout<<componenteBiconexe.size()<<'\n';
for(auto i: componenteBiconexe){
for(auto j : i){
fout<<j<<" ";
}
fout<<'\n';
}
}
int main() {
biconexInfoArena();
return 0;
}