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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
#include <cstdio>
#include <cinttypes>
#include <cassert>
#include <vector>
#include <unordered_set>

#define MAXN 200200
typedef long long ll;

typedef struct vertex {
  std::vector<int> outgoing;
  int pos;

  int outgoingFUs[2];  // The first two outgoing FUs in outgoing.
  int numoutgoingFUs;  // The size of the previous array.
  int nextprocessed;  // The next index to add to outgoingFUs from outgoing.
  int parent;  // The direct parent of this in the FU tree.
  int log_jumps[20];  // log_jumps[i] is the vertex (1<<i) moves up in the tree.
                      // This is filled in lazily, the fact it's not filled does _not_
                      // guarantee depth of the vertex is smaller than (1<<i).  
  int last_log_jump;  // log_jumps[last_log_jump] is set, while log_jumps[last_log_jump + 1] isn't. 
  int FU;  // The FU component this vertex belongs to (note, FU is not active, use FU(v).
  std::unordered_set<int> *FUcomponent;  // The elements of the FU;
  // The fields below are FU fields, and they're only valid in for the FU root.
  // The set of vertices with unresolved edges pointing at that FU. 
  // This is a pointer, because we'll do smaller-to-larger addition, which means
  // when merging FUs we might need to move the set to the new root (and join the previous
  // root set to it).
  std::unordered_set<int> *incoming; // One of two outgoingFUs hit here. 
  std::unordered_set<int> incoming_single; // The only outgoingFU hit here, but this isn't active yet. 
  // This is how much we should increase the value for hits to this vertex, for trees with a cycle.
  int cycle_size;  // If there's a cycle from the root, the size of the cycle.
  bool in_cycle;   // True, if the element is a part of a cycle.
} vertex;

vertex V[MAXN];
int N;
int current_limit; // The arena we're currently processing.
std::unordered_set<int> toCheck;

bool targetInOutgoingFUs(int target, int source) {
  if (V[source].numoutgoingFUs == 0) return false;
  if (V[source].outgoingFUs[0] == target) return true;
  if (V[source].numoutgoingFUs == 1) return false;
  if (V[source].outgoingFUs[1] == target) return true;
  return false;
}

// Find-Union, Get, Path-compression.
int FU(int v) {
  int cv = v;
  while (V[cv].FU != cv) {
    cv = V[cv].FU;
  }
  while (V[v].FU != v) {
    int nv = V[v].FU;
    V[v].FU = cv;
    v = nv; 
  } 
  return V[v].FU;
}

ll res;

// Try to jump length forward. It returns -1 on success (and V[v].log_jumps[length] is filled),
// or returns the distance from v to the root of FU(v), which is guaranteed to be smaller than 1 << length.
int tryjump(int v, int length) {
//fprintf(stderr, "TRYJUMP %d %d\n", v, length);
  if (v == FU(v)) return 0;  // I'm the root!
  // Now, last_log_jump has to be at least 0.
  assert(V[v].last_log_jump >= 0);  
  while (V[v].last_log_jump < length) {
    int next = V[v].log_jumps[V[v].last_log_jump];    
    int nextnext = tryjump(next, V[v].last_log_jump);
    if (nextnext != -1) return nextnext + (1 << V[v].last_log_jump);  // We can't go 1<<(llj+1) from v.
    V[v].log_jumps[V[v].last_log_jump+1] = V[next].log_jumps[V[v].last_log_jump];
    V[v].last_log_jump += 1;
  }
  return -1; 
}

// Same as tryjump, but asserts successful move and returns the target.
int forcejump(int v, int lgt) {
  int res = tryjump(v, lgt);
  assert(res == -1);
  return V[v].log_jumps[lgt];
}

// Calculate the depth of v in the FU tree.
int depth(int v) {
  int res = tryjump(v, 20);
  assert(res >= 0);
  return res;
}

// How many moves do I have to make till I reach something with in_cycle = true.
int find_cycle_depth(int v) {
//fprintf(stderr, "Finding cycle depth of %d\n", v);
  if (V[v].in_cycle) return 0;
  depth(v);  // Calculate all the logjumps.
  int res = 0;
  int maxjump = V[v].last_log_jump;
  while (maxjump >= 0) {
//fprintf(stderr, "Maxjumping by %d from %d\n", maxjump, v);
    if (V[v].last_log_jump < maxjump) maxjump = V[v].last_log_jump;
//fprintf(stderr, "V[%d].logjumps[%d] = %d, incycle = %d\n", v, maxjump, V[v].log_jumps[maxjump], (int) V[V[v].log_jumps[maxjump]].in_cycle);
    int next = V[v].log_jumps[maxjump];
    if (!V[next].in_cycle) {
      res += (1 << maxjump);
      v = next;
    } else {
      maxjump -= 1; 
    } 
  } 
  return res + 1;
}

// Move distance lgt, we know N is smaller than depth(v);
int move(int v, int lgt) {
  int cjump = 0;
  while (lgt) {
    if (!(lgt & (1 << cjump))) {
      cjump += 1;
      continue;
    }
    // Else, we should jump:
    v = forcejump(v, cjump);
    lgt -= (1 << cjump); 
  }
  return v;
}

int LCA(int v1, int v2) {
  assert(FU(v1) == FU(v2));
  int dv1 = depth(v1);
  int dv2 = depth(v2);
//fprintf(stderr, "LCA %d (depth %d) and %d (depth %d)\n", v1, dv1, v2, dv2);
  if (dv1 < dv2) { v2 = move(v2, dv2 - dv1); dv2 = dv1; } 
  if (dv1 > dv2) { v1 = move(v1, dv1 - dv2); dv1 = dv2; }
//fprintf(stderr, "After setting common depth, LCA %d (depth %d) and %d (depth %d)\n", v1, dv1, v2, dv2);
  assert(dv1 == dv2);
  if (v1 == v2) return v1;
  assert(dv1 > 0);

  int jumpdist = 0;
  while (dv1 >= (1 << jumpdist)) jumpdist += 1;
  jumpdist -= 1; 
  assert(jumpdist >= 0);
  // Phase 1. Find a jumpdist where they meet.
//fprintf(stderr, "Phase 1 start\n");
  while (true) {
    int nv1 = forcejump(v1, jumpdist);
    int nv2 = forcejump(v2, jumpdist);
    if (nv1 == nv2) break;
    v1 = nv1;
    v2 = nv2;
    dv1 -= (1 << jumpdist);
//fprintf(stderr, "DV1 %d, jumpdist %d\n", dv1, jumpdist);
    while (dv1 < (1 << jumpdist)) jumpdist -= 1; 
  }
  // Now, we know v1 != v2, but after jumping jumpdist, they are equal.
  assert(jumpdist >= 0);
  assert(v1 != v2);
//fprintf(stderr, "Phase 1 done\n");
  while (jumpdist) {
//fprintf(stderr, "Jumpdist %d, v1 %d, v2 %d\n", jumpdist, v1, v2);
    int nv1 = forcejump(v1, jumpdist - 1);
    int nv2 = forcejump(v2, jumpdist - 1);
    if (nv1 == nv2) {
      jumpdist -= 1; continue;
    } else {
      jumpdist -= 1; v1 = nv1; v2 = nv2;
    }
  }
//fprintf(stderr, "Phase 2 done\n");
  assert(v1 != v2);
  assert(jumpdist == 0);
  assert(forcejump(v1, 0) == forcejump(v2, 0));
//fprintf(stderr, "Returning LCA %d\n", forcejump(v1, 0));
  return forcejump(v1, 0);  
}

// We know all the edges from V hit the same FU component. Process.
void joinInto(int v) {
  //fprintf(stderr, "Joining into from %d\n", v);
   
  // Called only if we have only one outgoing FU.
  for (int i : V[v].outgoing) { 
    //fprintf(stderr, "Outgoing edge from %d to %d, which is in FU %d\n", v, i, FU(i));
    assert(FU(i) == FU(V[v].outgoing[0])); 
  }
  if (v > current_limit) return;  // We'll deal with it when it opens. 

  //fprintf(stderr, "It's real, we have data\n");
  // Regardless of what FU component this is, we need to find the LCA.
  // Note - there's a risk of doing this twice, but whatever.
  int target = V[v].outgoing[0];
  for (int i = 1; i < (int) V[v].outgoing.size(); ++i) {
    target = LCA(target, V[v].outgoing[i]);
  }
//fprintf(stderr, "Joining from %d to %d\n", v, target);
  if (target > current_limit) {
    V[target].incoming_single.insert(v);
    return; 
  }
  if (FU(target) == v) {
  //fprintf(stderr, "It's a cycle\n");
    assert(v == FU(v));
    int cdepth = depth(target);
    V[v].in_cycle = true;
    V[v].cycle_size = cdepth + 1;
    for (int ver = target; ver != v; ver = V[ver].parent) {
//fprintf(stderr, "Setting incycle for %d\n", ver);
      V[ver].in_cycle = true;
      V[ver].cycle_size = cdepth + 1;
    }    
    for (int i : *V[v].FUcomponent) {
//fprintf(stderr, "Fixing component %d\n", i);
      V[i].cycle_size = find_cycle_depth(i) + cdepth + 1;
//fprintf(stderr, "Fixed it, setting res\n");
      res += V[i].cycle_size - (depth(i) + 1); 
    }
    return;
  }
  // Last case - actual join.
  // OK, we join v to target.
//fprintf(stderr, "It's a real join\n");
  ll resdelta = V[v].FUcomponent->size(); 
  if (V[FU(target)].cycle_size >= 0) {
    resdelta *= V[target].cycle_size;
    for (int c : *V[v].FUcomponent) {
      V[c].cycle_size = V[target].cycle_size + depth(c) + 1;
    }
  } else {
    resdelta *= (depth(target) + 1);    
  } 
  res += resdelta;
  V[v].numoutgoingFUs = 0;  
  V[v].parent = target;
  V[v].log_jumps[0] = target;
  V[v].last_log_jump = 0;
  V[v].FU = FU(target);
  // Join FUcomponent items, smaller to larger.
  std::unordered_set<int> *smaller;
  std::unordered_set<int> *larger;
  if (V[v].FUcomponent->size() < V[FU(target)].FUcomponent->size()) {
    smaller = V[v].FUcomponent;
    larger = V[FU(target)].FUcomponent;
  } else {
    smaller = V[FU(target)].FUcomponent;
    larger = V[v].FUcomponent;
  }  
  for (int i : *smaller) {
    assert(larger->insert(i).second);
  }
  V[FU(target)].FUcomponent = larger;
  delete smaller;
  // Join incoming, smaller to larger. If an element repeats, it means we merged it's outgoing FUs, check.
  if (V[v].incoming->size() < V[FU(target)].incoming->size()) {
    smaller = V[v].incoming; larger = V[FU(target)].incoming;
  } else {
    smaller = V[FU(target)].incoming; larger = V[v].incoming;
  } 
  for (int i : *smaller) {
    bool success = larger->insert(i).second;
    if (!success) toCheck.insert(i);
  }
  V[FU(target)].incoming = larger;
  delete(smaller);
}

void compressOutgoingFUs(int v) {
  while (V[v].numoutgoingFUs == 2 && FU(V[v].outgoingFUs[0]) == FU(V[v].outgoingFUs[1])) {
    if (V[v].nextprocessed == (int) V[v].outgoing.size()) {
      V[v].numoutgoingFUs = 1;
    } else {
      V[v].outgoingFUs[1] = V[v].outgoing[V[v].nextprocessed++]; 
    } 
  } 
}

void check(int v) {
  if (v > current_limit) return;
  compressOutgoingFUs(v);
  //fprintf(stderr, "Compressed outgoing FUs for %d, currently have %d\n", v, V[v].numoutgoingFUs);
  if (V[v].numoutgoingFUs == 1) {
    joinInto(v);
  } else {
    V[FU(V[v].outgoingFUs[1])].incoming->insert(v);
  }
} 

void processVertex(int v) {
  current_limit = v;
  for (int i : V[v].incoming_single) {
    //fprintf(stderr, "Processing incoming single %d into %d\n", i, v);
    joinInto(i);
  }
  //fprintf(stderr, "Checking %d as it's the current limit\n", v);
  check(v);
  // Possibly there are things we need to process and compress as a result of joining.
  //fprintf(stderr, "Current size of toCheck: %d\n", (int) toCheck.size());
  while (!toCheck.empty()) {
    int val = *toCheck.begin();
    toCheck.erase(toCheck.begin());
    //fprintf(stderr, "Checking %d, because it's a double that just collapsed.\n", val);
    check(val);
  }    
}

int main() {
  scanf("%d", &N);
  for (int i = 0; i < N; ++i) {
    V[i].pos = i;
    V[i].numoutgoingFUs = 0;  
    V[i].nextprocessed = 0;
    V[i].parent = -1;
    for (int j = 0; j < 20; ++j) V[i].log_jumps[j] = -1; 
    V[i].last_log_jump = -1;
    V[i].FU = i;
    
    V[i].incoming = new std::unordered_set<int>();
    V[i].FUcomponent = new std::unordered_set<int>();
    V[i].FUcomponent->insert(i);   
    V[i].cycle_size = -1;
    V[i].in_cycle = false;
  }  
  // Process edges only after setting up all vertices.
  for (int source = 0; source < N; ++source) {
    int edges;
    scanf("%d", &edges);
//fprintf(stderr, "Vertex %d has %d edges\n", source, edges);
    V[source].outgoing.resize(edges);
    for (int j = 0; j < edges; ++j) {
      int target;
      scanf("%d", &target);
      target -= 1;
      V[source].outgoing[j] = target;
      if (V[source].numoutgoingFUs < 2 && !targetInOutgoingFUs(target, source)) {
        V[source].outgoingFUs[V[source].numoutgoingFUs] = target;  // Technically, V[target].FU, but that's same.
        V[source].numoutgoingFUs += 1;
        V[source].nextprocessed = j+1;          
      }
    } 
    assert(V[source].numoutgoingFUs > 0);
    assert(V[source].nextprocessed > 0);
  } 
  for (int v = 0; v < N; ++v) {
    if (V[v].numoutgoingFUs == 1) {
      V[V[v].outgoingFUs[0]].incoming_single.insert(v);    
    } else {
      V[V[v].outgoingFUs[0]].incoming->insert(v); 
      V[V[v].outgoingFUs[1]].incoming->insert(v);
    }
  }

  // OK, now process the arenas in increasing order.
  res = 0LL;
  for (int i = 0; i < N; ++i) {
    processVertex(i);
    if (i) printf(" "); 
    printf("%" PRId64, res);
    //fprintf(stderr, "\n Processing %d done\n", i); 
    //for (int k = 0; k < N; ++k) {
      //fprintf(stderr, "Vertex %d is currently in FU %d, at depth %d\n", k, FU(k), depth(k));
    //}
  }   
  printf("\n"); 
  return 0;
}