vector<int> G1[maxn], G2[maxn], s; //G1原图， G2反图
int vis[maxn] = { 0 }, color[maxn] = { 0 };
int iscc = 0;
int n, m;

void dfs1(int u) {
    vis[u] = true;
    for (int ne : G1[u]) {
        if (!vis[ne]) dfs1(ne);
    }
    s.push_back(u);
}

void dfs2(int u) {
    color[u] = iscc;
    for (int ne : G2[u]) {
        if (!color[ne]) dfs2(ne);
    }
}

void kosaraju() {
    iscc = 0;
    for (int i = 1; i <= n; i ++ ) {
        if (!vis[i]) dfs1(i);
    }
    for (int i = n; i >= 1; i -- ) {
        if (!color[s[i]]) {
            iscc ++;
            dfs2(s[i]);
        }
    }
}