SP83 BUNDLE - Bundling

Outel，一个知名的半导体公司，最近发布了一种新的名叫“铂金”的微处理器。就像很多现代的处理器一样，“铂金”能在一个时钟周期内处理多个互不依赖的指令（指令 $I_{2}$ 依赖于指令 $I_{1}$ 的一个例子： $I_{2}$ 从 $I_{1}$ 输出到的寄存器读取信息）。一些处理器聪明到能够计算哪些指令能够安全地并行执行。然而，“铂金”希望这些信息被明确指定。一个特殊标记——简单起见称之为“stop”，可能会在两条指令之间插入以表示“stop”之后的某些指令可能会依赖于“stop”之前的某些指令。换句话说，两个“stop”之间的指令相互之间不存在依赖关系，因此可以并行工作。 “铂金”的另一个有趣的特征就是一个指令序列必须被拆分成一条、两条或三条一组的连续指令。每一组都会被打包放进一种叫做“bundle”的容器里。每一个bundle有3个插槽，每一个插槽都可以存储一条单独的指令，可能存在空的插槽。每一条指令被归类为10个指令种类之一，用从A到J的连续大写字母表示（同类的指令具有相似的功能，比如A类都是整数运算指令而F类是其他什么稀奇古怪的指令类型，等等）。只有特定种类的指令会被允许放进同一个bundle里。每一个模板指定了一组允许存储在同一个bundle中的指令类型。一个模板也可以指定一个在bundle中出现stop的位置（最多只允许一个stop）。另外，stop可以出现在任意两个相邻的bundle之间。一组模板被称作一个捆绑配置文件。当把指令放进bundle里时，只能使用捆绑配置文件里的模板。 虽然“铂金”内置了指令缓存，但人们发现使它效率最高的关键在于尽可能密集地打包指令。除此之外，尽可能使用更少数量的“stop”。 你的任务是写一个程序用来给“铂金”打包指令。为简单起见我们假定指令不能重新排序。 #### 任务 编写一个程序以完成以下任务： 读取一个捆绑配置文件和一系列指令； 计算在不打破依赖关系的情况下这些指令能被打包成的最少的bundle数量和所需“stop”数量的最小值； 输出结果

输入的开头是一个整数 $z$ 代表测试数据组数，接下来有 $z$ 组测试数据。 对于每一组数据，第一行有两个以单个空格分隔的整数 $t(1\le t\le 1500)$ 和 $n(1\le n\le 100000)$ 。 $t$ 为捆绑配置文件中的模板数目， $n$ 是指令总数。 接下来的 $t$ 行每行描述一个模板，包含3个相连的大写字母 $t_{1},t_{2},t_{3}$ 和一个整数 $p(0\le p\le 2)$ 。字母 $t_{i}('A'\le t_{i} \le 'J')$ 表示第 $i$ 个插槽中允许的指令类型。 $p$ 表示在这个bundle中“stop”应该放在哪个插槽后面（0表示bundle里没有“stop”）。 接下来的 $n$ 行每行描述一条指令。第 $i$ 行包含一个大写字母 $c_{i}('A'\le c_{i} \le 'J')$ 表示第 $i$ 条指令的类型，以及一个整数 $d_{i}(0\le d_{i} < i)$ 表示被第 $i$ 条指令依赖的最后一条指令的编号（0表示这条指令不依赖于此前的任何一条指令）。 输入数据保证对于指令中出现过的每一个指令类型 $c$ ，至少有一个模板包含 $c$ 。

对于每一组测试数据，输出一行两个整数 $b$ 和 $s$ ，按顺序分别是合法打包方案下最少的bundle数目和所需“stop”数量的最小值。 感谢@fbhou 提供的翻译