在德克萨斯州的梅德福，Meemaw Cooper 花了很长时间准备了一棵美丽的圣诞树，上面装饰着非常特别的彩灯配置。但当 Meemaw 不在家时，她的孙女 Missy 不小心撞到了树，弄坏了彩灯。Missy 想在 Meemaw 回来之前恢复同样的彩灯配置，这就是为什么她向她的哥哥 Sheldon 求助，Sheldon 对彩灯的配置方式略知一二。

Sheldon 知道 Meemaw 买了很多相同配置的彩灯，并把它们放在了一起。一种彩灯配置可以看作一棵树（无向无环连通图），其中顶点是彩灯，边是连接它们的电线。每条边连接两个不同的彩灯，且边的集合构成一棵树。因此，Meemaw 买了很多相同配置的树，并添加了一些连接不同副本的电线，使得最终的配置也是一棵树。

Sheldon 很快向 Missy 解释了她需要做什么来恢复 Meemaw 的配置，他花了一下午的时间思考这个问题的一个推广。给定一个包含 $N$ 棵树的集合，确定对于每一棵树，集合中有多少棵其他的树可以生成它。如果可以通过连接一棵或多棵 $T_1$ 的副本并添加边，从而得到一棵与 $T_2$ 同构的树，则称树 $T_1$ 可以生成树 $T_2$。注意，不能移除任何边，只允许添加边。如果两棵树可以通过某种方式标记它们的顶点，使得它们变得完全相同，则称这两棵树是同构的。例如，具有边 $\{(1, 2), (2, 3)\}$ 的树与具有边 $\{(1, 3), (3, 2)\}$ 的树是同构的。

你能帮 Sheldon 解决他的问题吗？下图展示了一个包含 $N = 4$ 棵树的集合示例。在这种情况下，树 1 不能由集合中的任何其他树生成，树 2 可以由树 1 生成，树 3 可以由树 4 生成，树 4 可以由树 3 生成。

输入格式

第一行包含一个整数 $N$ ($2 \le N \le 2 \times 10^5$)，表示 Sheldon 正在考虑的树的数量。在此行之后，有 $N$ 组行，每组描述一棵树。

在描述一棵树的每组中，第一行包含一个整数 $K$ ($2 \le K \le 2 \times 10^5$)，表示树中的顶点数。顶点由 $1$ 到 $K$ 的不同整数标识。接下来的 $K - 1$ 行中的每一行包含两个整数 $U$ 和 $V$ ($1 \le U, V \le K$ 且 $U \neq V$)，表示该树有一条边 $(U, V)$。

所有树的顶点总数最多为 $4 \times 10^5$。

输出格式

输出一行，包含 $N$ 个整数，其中第 $i$ 个整数表示对于第 $i$ 棵输入树，输入中有多少棵其他的树可以生成该树。

样例

样例输入 1

4
4
1 2
1 3
1 4
8
1 2
1 3
1 4
5 6
5 7
5 8
1 5
2
1 2
2
2 1

样例输出 1

0 1 1 1