UOJ Logo Universal Online Judge

UOJ

附件下载 统计

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

一个有向图 Gn 个结点构成,第 i 个结点上写有一个大写英文字母 ai

定义一个回路 u0u1u2u(1)G 上的一条有向路径,使得 u0=u

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

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

假设所有 str(C) 构成的不可重集合叫做 S

你需要求出一个尽量长的字符串序列 s1,s2,,sk(k0),使得对于每个 i[1,k] 同时满足:

  1. siS
  2. si1<si
  3. 不存在一个字符串 sS 使得 si1<s<si

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

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

输入格式

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

第一行一个正整数 type,表示这个测试点属于子任务 type

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

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

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

  • 第一个字符 ai,表示结点 i 上写有的字母。
  • 之后一个自然数 degi,表示结点 i 的出边个数。
  • 之后 degi 个正整数 outi,1,outi,2,,outi,degi,表示结点 i 每条出边指向的结点。保证所有 outi,j<outi,j+1

输出格式

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

样例零

input

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

output

3
1
0

explanation

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

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

第二组数据中,S 包含所有由 AB 构成的存在非空循环节的无限字符串。可以证明 k=1

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

样例一~八

见附件下载,它们分别对应子任务 18

限制与约定

定义 m=i=1ndegi,表示 G 的有向边个数。

对于所有数据,保证 1T101n1050m3×105

子任务编号 子任务分值 n m 特殊性质 子任务依赖
1 13 10 30
2 13 100 300 1
3 13 1000 3000 12
4 9 105 3×105 对于所有 i,保证一定存在一个 outi,j=i
5 9 105 3×105 对于所有 i,保证一定存在一个 outi,j=(imodn)+1
6 13 105 3×105 保证 S 是一个有限集合
7 13 105 3×105 保证 ai{A,B} 中等概率独立选取
8 17 105 3×105 17

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

时间限制:6.5s

空间限制:512MB

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