#include <vector>
#include <stack>
#include <set>
#include <iostream>
using namespace std;

void dfsVisit(const vector<vector<int>> &g, vector<bool> &used, const int &v, stack<int> &nodes_stack){
    used[v] = true;
    for (const int &u : g[v]){
        if (!used[u]){
            dfsVisit(g, used, u, nodes_stack);
        }
    }
    nodes_stack.push(v);
}

void getNodesStack(const vector<vector<int>> &g, stack<int> &nodes_stack){
    vector<bool> used(g.size(), false);
    for (int v = 0; v < g.size(); ++v){
        if (!used[v]){
            dfsVisit(g, used, v, nodes_stack);
        }
    }
}

void getTranspose(const vector<vector<int>> &g, vector<vector<int>> &gr){
    for (int v = 0; v < g.size(); ++v){
        for (const int &u : g[v]){
            gr[u].push_back(v);
        }
    }
}

void getComponent(const vector<vector<int>> &gr, vector<bool> &used, const int &v,
        vector<int> &component, vector<int> &colors, const int &color){
    used[v] = true;
    colors[v] = color;
    component.push_back(v);
    for (const int &u : gr[v]){
        if (!used[u]){
            getComponent(gr, used, u, component, colors, color);
        }
    }

}
void getSCC(const vector<vector<int>> &g, vector<vector<int>> &components, vector<int> &colors){
        stack<int> nodes_stack;
        getNodesStack(g, nodes_stack);
        vector<vector<int>> gr(g.size());
        getTranspose(g, gr);
        vector<bool> used(gr.size(), false);
        int color = 0;
        while (!nodes_stack.empty()){
            int v = nodes_stack.top();
            nodes_stack.pop();
            if (!used[v]){
                vector<int> newComponent;
                getComponent(gr, used, v, newComponent, colors, color++);
                components.push_back(newComponent);
            }
        }
}

void printComponents(const vector<vector<int>> &components){
    for (int i = 0; i < components.size(); ++i){
        cout << "SCC " << i << ":   ";
        for (auto v : components[i]){
            cout << v << ' ';
        }
        cout << endl;
    }
}

void getMetaGraph(const vector<vector<int>> &g, const vector<int> &colors, vector<set<int>> &metaGraph){
    for (int v = 0; v < g.size(); ++v){
        for (auto u : g[v]){
            if (colors[v] != colors[u]){
                metaGraph[colors[v]].insert(colors[u]);
            }
        }
    }
}

void printMetaGraph(const vector<set<int>> &metaGraph){
    cout << "Meta-graph:\n";
    for (int v = 0; v < metaGraph.size(); ++v){
        cout << v << "   ";
        for (auto u : metaGraph[v]){
            cout << u << ' ';
        }
        cout << endl;
    }
}