#include <cstring>
#include <vector>
#include <stack>
using namespace std;
#define MP(a, b)       make_pair((a), (b))
#define MAXN 1000

 
struct SCC
{
    // 默认图是在外部声明的全局变量 vector<int> g[maxn]
    // scc_id 是每个点的scc编号 从1开始
    int dfn[MAXN], low[MAXN], scc_id[MAXN], n, dfst, scc_cnt;
    stack<int> st;
    void find_scc(int n)
    {
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(scc_id, 0, sizeof(scc_id));
        this->n = n;
        dfst = 0;
        scc_cnt = 0;
        while (!st.empty())         st.pop();
        for (int i=0; i<n; ++i)
            if (!dfn[i])
                dfs(i);
    }
    void dfs(int u)
    {
        dfn[u] = low[u] = ++dfst;
        st.push(u);
        for (int i=0; i<(int)g[u].size(); ++i)
        {
            int v = g[u][i];
            if (!dfn[v])
            {
                dfs(v);
                low[u] = min(low[u], low[v]);
            }
            else if (!scc_id[v])
                low[u] = min(low[u], dfn[v]);
        }
        if (low[u] == dfn[u])
        {
            ++scc_cnt;
            for (; ;)
            {
                int x = st.top();
                st.pop();
                scc_id[x] = scc_cnt;
                if (x == u)         break;
            }
        }
    }
};