vector<long long> topo_sort(const vector<vector<long long>> &G)
{ // bfs
    vector<long long> ans;
    long long n = (long long)G.size();
    vector<long long> ind(n); // ind[i]: 頂点iに入る辺の数(次数)
    for (long long i = 0; i < n; i++)
    { // 次数を数えておく
        for (long long next : G[i])
        {
            ind[next]++;
        }
    }
    queue<long long> que;
    for (long long i = 0; i < n; i++)
    { // 次数が0の点をキューに入れる
        if (ind[i] == 0)
            que.push(i);
    }
    while (!que.empty())
    { // 幅優先探索
        long long now = que.front();
        ans.push_back(now);
        que.pop();
        for (long long next : G[now])
        {
            ind[next]--;
            if (ind[next] == 0)
            {
                que.push(next);
            }
        }
    }
    return ans;
}
//DAGの最長パスの長さ(最長パスに使われる辺の数)を返す
long long long_path(const vector<vector<long long>> &G)
{
    long long n = G.size();
    vector<long long> topo = topo_sort(G);
    reverse(topo.begin(), topo.end());
    vector<long long> dp(n, 0);
    long long ret = 0;
    //後ろから更新していく
    for (long long i : topo)
    {
        for (long long j : G[i])
        {
            dp[i] = max(dp[i], dp[j] + 1);
        }
        ret = max(ret, dp[i]);
    }
    return ret;
}