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
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const int nax = 200 * 1000 + 10, INF = 1e9 + 10;
int n;
vi V[nax], Vrev[nax];
ll ans[nax];
bool vis[nax];
vi topo;
int scc[nax], nr, bad[nax], cnt[nax], reach[nax];

void dfs(int x) {
	vis[x] = true;
	for(int nbh : V[x]) if(!vis[nbh]) {
		dfs(nbh);
	}
	topo.PB(x);
}

void dfsrev(int x) {
	vis[x] = true;
	scc[x] = nr;
	cnt[nr]++;
	for(int nbh : Vrev[x]) if(!vis[nbh]) {
		dfsrev(nbh);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int k, i = 1; i <= n; ++i) {
		cin >> k;
		for(int x, j = 0; j < k; ++j) {
			cin >> x;
			V[i].PB(x);
			Vrev[x].PB(i);
		}
	}
	for(int u = 1; u <= n; ++u) {
		for(int v = 1; v <= n; ++v) {
			vis[v] = false;
		}
		dfsrev(u);
		cnt[0] = 0;
		for(int v = 1; v <= n; ++v) {
			reach[v] = vis[v];
		}
		for(int v = 1; v <= n; ++v) {
			vis[v] = false;
		}
		vis[u] = 1;
		topo.clear();
		for(int v = 1; v <= n; ++v) {
			if(!vis[v]) {
				dfs(v);
			}
		}
		for(int v = 1; v <= n; ++v) {
			vis[v] = false;
			cnt[v] = 0;
		}
		vis[u] = true;
		scc[u] = 0;
		nr = 0;
		for(int v = n - 2; v >= 0; --v) {
			if(!vis[topo[v]]) {
				nr++;
				dfsrev(topo[v]);
			}
		}
		for(int i = 1; i <= nr; ++i) {
			bad[i] = 0;
		}
		bad[0] = 0;
		for(int i = 0; i < n - 1; ++i) {
			int v = topo[i];
			if(!reach[v]) {
				bad[scc[v]] = n;
				continue;
			}
			bad[scc[v]] = max(bad[scc[v]], v - 1);
			for(int nbh : V[v]) {
				if(scc[nbh] == scc[v]) bad[scc[v]] = n;
				else bad[scc[v]] = max(bad[scc[v]], bad[scc[nbh]]);
			}
		}
		for(int i = 1; i <= nr; ++i) {
			ans[max(bad[i], u - 1)] += cnt[i];
		}
	}
	for(int i = n - 1; i >= 0; --i) {
		ans[i] += ans[i + 1];
	}
	for(int i = 1; i <= n; ++i) {
		cout << (ll)n * (n - 1) - ans[i] << " ";
	}	
}