1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>


using namespace std;


vector <long long> solve(int n, vector <vector<int>> &g, vector <vector<int>> &gRev) {
    vector <long long> ans(n, 0);
    vector <int> numGood(n, 0);
    vector <vector<int>> deg(n, vector <int> (n));

    for (int v = 0; v < n; v++) {
        for (int u = 0; u < n; u++) {
            deg[v][u] = g[u].size();
        }
    }

    for (int r = 0; r < n; r++) {
        for (int v = 0; v <= r; v++) if (v == r || deg[v][r] == 0) {
            queue <int> q;
            q.push(r);

            while (!q.empty()) {
                int u = q.front(); q.pop();
                if (u != v) {
                    numGood[u]++;
                }

                for (int p : gRev[u]) if (p != v) {
                    deg[v][p]--;
                    if (p <= r && deg[v][p] == 0) {
                        q.push(p);
                    }
                }
            }
        }

        for (int v = 0; v < n; v++) {
            ans[r] += numGood[v];
        }
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

    vector <vector<int>> g(n), gRev(n);
    for (int v = 0; v < n; v++) {
        int l;
        cin >> l;

        while (l--) {
            int u;
            cin >> u; u--;

            g[v].push_back(u);
            gRev[u].push_back(v);
        }
    }

    auto ans = solve(n, g, gRev);
    for (long long &x : ans) {
        cout << x << ' ';
    }

    return 0;
}