描述

一位计算机科学专业的学生正在研究从不同大学毕业所需的学期数。每所大学都提供了一份必修课程清单，包括这些课程的先修条件以及每门课程的开课学期。根据这些信息，确定毕业所需的最短学期数。

考虑以下示例：学生需要修读$4$门课程：$mt42$、$cs123$、$cs456$和$cs789$。$mt42$仅在秋季学期开设且没有先修课程；$cs123$仅在春季学期开设且没有先修课程；$cs456$仅在春季学期开设，其先修课程为$cs123$和$mt42$；$cs789$在秋季和春季学期都开设，唯一的先修课程是$cs456$。最短毕业时间为$5$个学期：秋季修读$mt42$，次年春季修读$cs123$，第三年春季修读$cs456$（因为它不在秋季开设），第四年秋季修读$cs789$。

本题中只有秋季和春季两个学期，学期计数从秋季开始。

此外还有一个额外限制：为了保持宿舍入住率，每所大学对每学期可修课程数量设置了上限。该限制作为输入数据的一部分给出。第三个示例展示了这种情况。

输入

包含$1$到$25$个数据集，最后一行仅包含$-1\ -1$。每个数据集的第一行是两个正整数$n$和$m$（$1 \leq n \leq 12$表示课程数量，$2 \leq m \leq 6$表示每学期最多修读课程数），接着一行列出$n$个课程编号（由$1$$-$$5$位字母或数字组成）。随后$n$行描述各课程信息，包括：课程编号、开课学期（$F$=秋季，$S$=春季，$B$=两学期均开）、先修课程数量$p$（$0 \leq p \leq 5$）以及具体的$p$个先修课程编号。第一个示例对应上述问题描述。

输出

对每个数据集输出一行结果，格式见示例。

输入数据 $1$

4 6
cs123 mt42 cs456 cs789
mt42 F 0
cs123 S 0
cs456 S 2 cs123 mt42
cs789 B 1 cs456
3 6
math1 comp2 comp3
comp3 S 1 comp2
math1 S 0
comp2 F 1 math1
4 3
m10 m20 c33 c44
m10 B 0
m20 B 0
c33 B 0
c44 B 0
-1 -1

输出数据 $1$

The minimum number of semesters required to graduate is 5.
The minimum number of semesters required to graduate is 4.
The minimum number of semesters required to graduate is 2.

来源

2005年美国中北部地区竞赛