大样例

King of Spades, looping letters bound in endless strings, questing for their place.

一个有向图 $G$ 由 $n$ 个结点构成，第 $i$ 个结点上写有一个大写英文字母 $a_i$。

定义一个回路 $u_0\to u_1\to u_2\to\cdots\to u_ℓ(ℓ\geq1)$ 是 $G$ 上的一条有向路径，使得 $u_0=u_ℓ$。

注意：一个回路可以经过任何一个结点任意多次，唯一的限制是需要满足回路的起点等于终点。

对于 $G$ 的每个回路 $C$，从它的起点开始，按照顺序读出 $C$ 中所有结点上面的字母，反复循环，可以得到一个没有穷尽的字符串 $\text{str}(C)$。

假设所有 $\text{str}(C)$ 构成的不可重集合叫做 $S$。

你需要求出一个尽量长的字符串序列 $s_1,s_2,\cdots,s_k(k\geq0)$，使得对于每个 $i\in[1,k]$ 同时满足：

1. $s_i\in S$；
2. $s_{i-1} < s_i$；
3. 不存在一个字符串 $s'\in S$ 使得 $s_{i-1} < s' < s_i$。

其中两个字符串 $s < t$ 表示 $s$ 的字典序小于 $t$。$s_0$ 被认为是字典序小于一切的。

你只需要输出这个 $k$ 的最大值，不需要输出具体的字符串序列。

输入格式

本题一个测试点内有多组测试数据。

第一行一个正整数 $\text{type}$，表示这个测试点属于子任务 $\text{type}$。

第二行一个正整数 $T$，表示这个测试点内测试数据的组数。对于每组测试数据：

第一行一个正整数 $n$，表示有向图 $G$ 的结点个数。

之后 $n$ 行，其中的第 $i$ 行表示 $G$ 中第 $i$ 个结点的信息。具体来说：

• 第一个字符 $a_i$，表示结点 $i$ 上写有的字母。
• 之后一个自然数 $\text{deg}_i$，表示结点 $i$ 的出边个数。
• 之后 $\text{deg}_i$ 个正整数 $\text{out}_{i,1},\text{out}_{i,2},\cdots,\text{out}_{i,\text{deg}_i}$，表示结点 $i$ 每条出边指向的结点。保证所有 $\text{out}_{i,j}<\text{out}_{i,j+1}$。

输出格式

对于每组数据，只需要输出一行一个自然数 $k$，表示你求出的字符串序列的最大长度。

1
3
3
A 1 2
B 1 3
C 1 1
2
A 2 1 2
B 2 1 2
3
A 2 2 3
A 0
A 0

3
1
0

在这个样例的第一组数据中，$S=\{\text{ABCABC......},\text{BCABCA......},\text{CABCAB......}\}$，因此 $k=3$。

注意即使点集和边集都相同，选择不同的起点得到的是不同的回路，继而可能读出不同的字符串。

第二组数据中，$S$ 包含所有由 $\text{A}$ 和 $\text{B}$ 构成的存在非空循环节的无限字符串。可以证明 $k=1$。

第三组数据中，由于 $G$ 是一棵叶向树，图中没有回路，$S=\varnothing$。当然 $k=0$。

样例一～八

见附件下载，它们分别对应子任务 $1\sim8$。

限制与约定

定义 $m=\displaystyle\sum_{i=1}^n\text{deg}_i$，表示 $G$ 的有向边个数。

对于所有数据，保证 $1\leq T\leq10$，$1\leq n\leq10^5$，$0\leq m\leq3\times10^5$。

子任务 $7$ 的数据中有向图 $G$ 的形态不保证随机。我们一共生成了 $1.8\times10^4$ 组数据，按照一定的标准筛选出了 $90$ 组数据，填充子任务 $7$ 的 $9$ 个测试点。因此对你的正确率要求可能很高。

时间限制：$6.5\texttt{s}$

空间限制：$512\texttt{MB}$

请你注意：对于赛后添加的 hack 数据，我们只会检查 $\text{type}\in[1,8]$，不会检查这个测试点是否满足子任务 $\text{type}$ 的限制。