#include <bits/stdc++.h>
using namespace std;

struct edge{
    int x,y;
    int curr_flow;
    int max_flow;
};

class Graph{
private:
        int n; //nr de noduri, nr de muchii, nodul de inceput
        int m; // nr de muchii
//        int s; // folosit la bfs, nodul de start
        bool type; //0 = neorientat; 1 = orientat
        bool capacity;
        bool flow;
        vector<vector <int>> adj; // adj = adjacent (=liste de vecini)
        vector < vector<int> > comp_nmbr; // folosit la biconexe, vector de vectori ce reprezinta componentele biconexe
        vector < vector<edge> > adj_flow;

public:
    Graph(string fname, bool type, bool flow);

    void BFS(int start);

    void DFS();

    void biconex();
    void DFS_biconex(int node, int low[], int disc[], int parent[], bool visited[], int time,stack <pair<int,int> >& st  );

    void TS(int node, bool visited[], stack<int>& sorted_nodes); //sortare topologica
    void TS_read();

    void APM();

    void MaxFlux();


};

Graph::Graph(string fname, bool type, bool flow){
    ifstream fin(fname);
    this->type = type;
    this->flow = flow;


//    if(this->type)
//    {
//        fin>>this->n>>this->m;
//        int x,y;
//        adj.resize(n+1);
//
//        for(int i = 0; i < m; i++)
//        {
//            fin>>x>>y;
//            adj[x].push_back(y);
//        }
//
//        fin.close();
//    }else{
//        fin>>this->n>>this->m;
//        int x,y;
//        adj.resize(n+1);
//
//        for(int i = 0; i < m; i++)
//        {
//            fin>>x>>y;
//            adj[x].push_back(y);
//            adj[y].push_back(x);
//        }
//    fin.close();
//    }

    switch(this->type){
case true:
        if(this->flow)
        {
                fin>>this->n>>this->m;
                int x,y,flow;
                edge e;
                for(int i = 0; i < m; i++)
                {
                    fin>>x>>y>>flow;
                    e.x = x;
                    e.y = y;
                    e.max_flow = flow;
                    e.curr_flow = 0;
                    adj_flow[e.x].push_back(e);
                }
                fin.close();
        }else{
            fin>>this->n>>this->m;
            int x,y;
            adj.resize(n+1);

            for(int i = 0; i < m; i++)
            {
                fin>>x>>y;
                adj[x].push_back(y);
            }

            fin.close();

            }
        break;

case false:
        fin>>this->n>>this->m;
        int x,y;
        adj.resize(n+1);

        for(int i = 0; i < m; i++)
        {
            fin>>x>>y;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
    fin.close();
    break;

    }
}

void Graph::APM(){
    ifstream fin("apm.in");
    fin>>n>>m;
    vector<pair<int,int>> apm_adj[20010];
    int x,y,c;

    for(int i = 0; i < m; i++){
        fin>>x>>y>>c;
        apm_adj[x].push_back(make_pair(y,c));
        apm_adj[y].push_back(make_pair(x,c));

    }
    fin.close();

//    for(int v = 1; v <= n; v++){
//        for(unsigned int j = 0; j< apm_adj[v].size(); j++ ){
//            cout<<v<<": "<<apm_adj[v][j].first<< " "<<apm_adj[v][j].second<<",\n";
//        }
//        cout<<"\n";
//    }

    priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > pq;
    vector<bool> inAPM(n+1,false);
    vector<int> weight(n+1, 1100);
    vector<int> parent(n+1,-1);

    int start = 1;
    int s = 0;
    pq.push(make_pair(0,start));
    weight[start] = 0;
    while (!pq.empty()){

        int u = pq.top().second;

        pq.pop();
        if(inAPM[u] == true){
            continue;
        }
        inAPM[u] = true;


        for (auto x : apm_adj[u]){
            int v = x.first;
            int w = x.second;

            if(inAPM[v] == false && w < weight[v]){
                weight[v] = w;
                pq.push(make_pair(weight[v],v));
                parent[v] = u;
            }
        }
    }
    ofstream fout("apm.out");
    for(int i = 2; i <=n; i++){
        s+=weight[i];
    }
    fout<<s<<"\n"<<n-1<<"\n";

        for(int i = 2; i <=n; i++){
        fout<<parent[i] <<" "<<i<<"\n";
    }






}

void Graph::TS_read(){

    if (!this->type){
        cout<<("Topological sorting works only on oriented graphs!\n");
        exit(NULL);
    }

    stack<int> sorted_nodes;
    bool* visited = new bool[n+1];

    for(int i = 0; i <= n; i++){
        visited[i] = false;
    }

    for(int i = 1; i <= n; i++){
        if(!visited[i]){
            TS(i, visited, sorted_nodes);
        }

    }
    ofstream fout("sortaret.out");
    while(!sorted_nodes.empty()){
        fout<<sorted_nodes.top()<<" ";
        sorted_nodes.pop();
    }
    fout.close();
}

void Graph::TS(int node, bool visited[], stack<int>& sorted_nodes){
    visited[node] = true;

    for(auto it: adj[node]){
        if(!visited[it]){
            TS(it, visited, sorted_nodes);
        }

    }
    sorted_nodes.push(node);
}

void Graph::biconex(){

    if (this->type){
        cout<<("Biconex components exist only in unoriented graphs!\n");
        exit(NULL);
    }

    stack < pair<int,int> > st;
    int *disc = new int[n+1];
    int *low = new int[n+1];
    int *parent = new int[n+1];
    bool visited[n+1] = {0};
    int time = 0;

    for (int i = 1; i <= n; i++){
        disc[i] = -1;
        low[i] = -1;
        parent[i] = -1;
    }

    for (int i = 1; i <= n; i++){
        if (visited[i] == false){
            DFS_biconex(i, low, disc, parent, visited, time, st);
        }

    }
    ofstream fout("biconex.out");
    fout<<comp_nmbr.size()<<"\n";

    for(auto comp : comp_nmbr){
        for(auto node: comp){
            fout<<node<<" ";
        }
        fout<<"\n";
    }
    fout.close();

}

void Graph::DFS_biconex(int node, int low[], int disc[], int parent[], bool visited[], int time,stack <pair<int,int> >& st  ){
    disc[node] = time + 1; //timpul de descoperire in dfs
    low[node] = time + 1;
    time++;
    visited[node] = 1;
    int children = 0;

    for(int i: adj[node] ){

        if (visited[i] == false){
            children++;
            st.push({node,i});
            parent[i] = node;
            DFS_biconex(i, low, disc, parent, visited, time, st);
            low[node] = min(low[node], low[i]);

            if( (parent[node] == -1 && children > 1) || (disc[node] != -1 && low[i] >= disc[node] ) )
            {       /*^radacina                                ^restul nodurilor*/
                vector <int> components; // vector ajutator in care va fi stocata componenta biconexa curenta
                while(st.top().first != node && st.top().second != i){
                        components.push_back(st.top().second);
                        st.pop();
                }
                components.push_back(st.top().second);
                components.push_back(st.top().first);
                st.pop();
                comp_nmbr.push_back(components);

            }

        }else if (parent[node] != i && disc[i] < low[node]  ){
                    low[node] = disc[i];
                }
    }

}



void Graph::DFS(){
    bool visited[n+1] = {0};
    queue<int> q;
    int conex = 0;

    for(int i = 1; i < n+1; i++){
        if(!visited[i]){
            conex++;
            q.push(i);
            while( !q.empty() ){
                int curr_node = q.front();
                visited[curr_node] = 1;
                q.pop();
                for(unsigned int j = 0; j < adj[curr_node].size(); j++){
                    if(!visited[ adj[ curr_node][j] ] )
                        q.push(adj[curr_node][j] );
                }
            }
        }
    }
    ofstream fout("dfs.out");
    fout<<conex;
    fout.close();

}


void Graph::BFS(int start){
    bool visited[n+1];
    int length[n+1];

    for(int i = 0; i < n+1; i++){
        visited[i] = false;
        length[i] = -1;
    }

    visited[start] = true;
    length[start] = 0;

    queue<int> q;
    q.push(start);

    while(!q.empty()){
        int curr_node = q.front();
        q.pop();
        int nr_vec = adj[curr_node].size();

        for(int i = 0; i<nr_vec;i++){
            int x = adj[curr_node][i];

            if(!visited[x]){
                visited[x] = true;
                q.push(x);
                length[x] = length[curr_node] + 1;
            }
        }
    }

    ofstream fout("bfs.out");
    for(int i = 1; i <= n; i++){
        fout<<length[i]<<" ";
    }
    fout.close();
}

int main()
{
    int x = 2;
    Graph test("biconex.in",0,0);
    test.biconex();

    return 0;
}