#include #include #include #include using namespace std; #define rep(i,n) for(int i=0; i> N; vector> edges(N-1); vector deg(N); rep(u,N){ cin >> deg[u]; rep(k,deg[u]){ int e; cin >> e; e--; edges[e].first = u; swap(edges[e].first, edges[e].second); } } vector degtmp = deg, adjsum(N), ord; rep(v,N) if(degtmp[v] == 1) ord.push_back(v); for(auto [u,v] : edges) adjsum[u] ^= v; for(auto [u,v] : edges) adjsum[v] ^= u; rep(i,N-1){ int v = ord[i]; int w = adjsum[v]; adjsum[w] ^= v; if(--degtmp[w] == 1) ord.push_back(w); } vector par = move(adjsum); par[ord.back()] = -1; vector listL(N+1), listR(N+1); rep(i,N-1) listL[ord[i + 1]] = ord[i]; rep(i,N-1) listR[ord[i]] = ord[i + 1]; listR[N] = ord[0]; listL[ord[0]] = N; listR[ord[N-1]] = N; listL[N] = ord[N-1]; vector dp_child_use(N); for(int k=1; k<=N-1; k++){ int ans = 0; for(int v=listR[N]; v!=N; v=listR[v]){ int w = par[v]; int has_parent = w >= 0 ? 1 : 0; int num_children = deg[v] - has_parent; int use_up_edge = 0; if(k <= num_children - dp_child_use[v]){ ans += 1; } else if(has_parent && k <= num_children - dp_child_use[v] + 1){ ans += 1; use_up_edge += 1; } if(has_parent && deg[w] >= k){ dp_child_use[w] += use_up_edge; } dp_child_use[v] = 0; if(deg[v] == k){ listR[listL[v]] = listR[v]; listL[listR[v]] = listL[v]; v = listL[v]; } } if(k != 1) cout << " "; cout << ans; } cout << "\n"; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); testcase(); return 0; }