题目描述

Gusteru 在柜子里发现了一款古老的冒险游戏，名为 Ijnamuj。游戏从第 $1$ 关开始，目标是尽可能完成更多关卡。

每个关卡 $i$ 都有一个关联列表 $l(i)$，其中包含若干其他关卡。若要完成关卡 $i$，Gusteru 必须先完成列表 $l(i)$ 中的所有关卡，顺序不限。

每完成一个关卡后，他可以继续完成任意一个满足条件的关卡：该关卡的列表中只包含已经完成的关卡。

由于游戏从第 $1$ 关开始，因此 $l(1)$ 总是空列表，也就是说完成第 $1$ 关不受任何其他关卡限制。

任务

求 Gusteru 最多可以完成多少个关卡。

输入格式

第一行包含一个整数 $T$，表示测试场景的数量。

对于每个测试场景，输入格式如下：

• 第一行包含一个整数 $N$，表示该场景中的关卡数；
• 接下来 $N$ 行描述 $N$ 个列表。第 $i$ 行先给出一个整数 $k_i$，表示关卡 $i$ 的列表长度，随后给出 $k_i$ 个整数，表示列表中关卡的编号。

输出格式

应包含 $T$ 行。

第 $i$ 行输出第 $i$ 个测试场景的答案。

数据范围与限制

• $1\le T\le 5$；
• $1\le N\le 500\,000$；
• $k_1=0$；
• $0\le k_i\le N-1$；
• 对任意 $1\le i\le N$，都有 $i\notin l(i)$；
• 在一个测试场景中，$k_1+k_2+\cdots+k_N\le 4N$；
• 在所有 $T$ 个测试场景中，上述所有 $k_i$ 之和不超过 $5\,000\,000$。

定义一个循环依赖为一个关卡序列 $a_1,a_2,\ldots,a_p$，其中 $2\le p\le N$，并满足：

$$a_1\in l(a_2),\ a_2\in l(a_3),\ \ldots,\ a_{p-1}\in l(a_p),\ a_p\in l(a_1).$$

子任务

子任务	分值	限制
1	17	$1\le N\le 10$
2	19	所有循环依赖长度恰好为 $2$，且 $N\le 2000$
3	33	$1\le N\le 2000$
4	31	无额外限制

样例

输入

2
5
0
1 1
1 2
2 3 5
1 4
6
0
2 4 6
2 2 5
1 3
1 1
1 5

输出

3
3

解释

共有 $T=2$ 个场景。

在第一个场景中，唯一可以无条件到达的关卡是第 $1$ 关。第 $1$ 关可以解锁第 $2$ 关，第 $2$ 关又可以解锁第 $3$ 关。之后无法再解锁其他关卡，因为第 $4$ 关需要第 $3$ 关和第 $5$ 关，而第 $5$ 关又依赖第 $4$ 关。因此最多只能完成 $3$ 个关卡，即第 $1,2,3$ 关。

第二个场景类似，最多可以完成 $3$ 个关卡，即第 $1,5,6$ 关。