struct BCC
{
    int dfn[maxn], low[maxn], bccno[maxn], n, bcc_cnt;
    bool isCut[maxn];
    vector<int> keyV, bcc[maxn];
    vector<pair<int, int> > keyE;
    stack<int> st;
    BCC(int _n=0)
    {
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(isCut, 0, sizeof(isCut));
        keyV.clear(), keyE.clear();
        n = _n;
        bcc_cnt = 0;
    }
    void find_bbc()
    {
        for (int i=0; i<n; ++i)
            if (!dfn[i])
                dfs(i, 1);
    }
    int dfs(int u, int cnt)
    {
        int &lowu = low[u];
        lowu = dfn[u] = cnt;
        st.push(u);
        int part = cnt > 1;
        rep(i, (int)g[u].size())
        {
            int v = g[u][i];
            if (!dfn[v])
            {
                int lowv = dfs(v, cnt+1);
                lowu = min(lowu, lowv);
                if (lowv > dfn[u])
                    keyE.push_back(make_pair(u, v));
                if (lowv >= dfn[u])
                {
                    if (++part == 2)
                        keyV.push_back(u), isCut[u] = true;;
                    bcc[++bcc_cnt].clear();
                    bcc[bcc_cnt].push_back(u);
                    while (!st.empty())
                    {
                        int now = st.top();
                        st.pop();
                        bcc[bcc_cnt].push_back(now);
                        if (now == v)    break;
                    }
                }
            }
            else if (dfn[v] < dfn[u] && dfn[v] != dfn[u]-1)  // 用反向边更新lowu  注意不是树边！
            {
                lowu = min(lowu, dfn[v]);
            }
        }
        return lowu;
    }
}; 

struct BCC
{
    int dfn[maxn], low[maxn], bccno[maxn], n, bcc_cnt;
    bool isCut[maxn];
    vector<int> keyV, bcc[maxn];
    vector<pair<int, int> > keyE;
    int st[maxn], top;
    BCC(int _n=0)
    {
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(isCut, 0, sizeof(isCut));
        keyV.clear(), keyE.clear();
        n = _n;
        bcc_cnt = 0;
        top = 0;
    }
    void find_bbc()
    {
        for (int i=0; i<n; ++i)
            if (!dfn[i])
                dfs(i, 1);
    }
    int dfs(int u, int cnt)
    {
        int &lowu = low[u];
        lowu = dfn[u] = cnt;
        st[top++] = u;
        int part = cnt > 1;
        rep(i, (int)g[u].size())
        {
            int v = g[u][i];
            if (!dfn[v])
            {
                int lowv = dfs(v, cnt+1);
                lowu = min(lowu, lowv);
                if (lowv > dfn[u])
                    keyE.push_back(make_pair(u, v));
                if (lowv >= dfn[u])
                {
                    if (++part == 2)
                        keyV.push_back(u), isCut[u] = true;;
                    bcc[++bcc_cnt].clear();
                    bcc[bcc_cnt].push_back(u);
                    for (st[top] = 0; st[top] != v; bcc[bcc_cnt].push_back(st[--top]));
                }
            }
            else if (dfn[v] < dfn[u] && dfn[v] != dfn[u]-1)
            {
                lowu = min(lowu, dfn[v]);
            }
        }
        return lowu;
    }
};