题目描述

给定一张有向图，每个点至少有一条出边，每个点只可能被染成黑色或白色。

你需要对于所有 $1 \leq k \leq n$ 求出以下问题的答案：

• 初始状态下所有点均为白色。
• 每一次操作，Alice 先选择一个黑点 $1 \leq u \leq k$，Bob 必须从 $u$ 出边指向的点中选择一个将其染黑。
• Alice 和 Bob 在这张图上玩游戏，定义一个有序二元组 $(A, B)$ 是好的，如果 $A \neq B$ 且 Alice 从只有 $A$ 点为黑色的状态开始，无论 Bob 如何操作，$B$ 点均可以变成黑色。
• 求好的有序二元组的个数。

输入格式

第一行，一个整数 $n$；

接下来 $n$ 行，其中第 $i$ 行先是一个整数 $l$，接下来 $l$ 个整数 $p_1, p_2, \cdots, p_l$，表示 $i$ 的出边指向的点。

输出格式

一行，$n$ 个整数，其中第 $i$ 个整数表示 $k = i$ 时的答案。

9
2 2 3
1 1
1 2
1 5
3 5 8 9
1 5
2 6 4
2 5 9
3 5 8 5

0 1 4 4 5 6 7 7 7

提示

对于 $100\%$ 的数据，$2 \leq n \leq 2 \times 10^5$，$1 \leq l \leq 5 \times 10^5$，$n \leq \sum l \leq 5 \times 10^5$，不保证无重边，但保证无自环。