#描述#
牛逼的学生总会对提早毕业感兴趣，大学会为该生提供一系列课程，包括课程的前提课程（只有得到全部前提课程的学分才可学习该门课程）和开课季度。得到这些信息后，可以计算出最少上几个学期的课就可以毕业。
考虑下面的例子，一个学生需要上4门课，mt42, cs123, cs456和cs789。mt42只在秋季开课，没有前提课程。cs123只在春季开课，没有前提课程。cs456只在春季开课，cs123和mt42是它的前提课程。cs789在春季和秋季都有开课，cs456是它的前提课程。最短可以毕业的时间是5个学期，秋季上mt42，下个春季上cs123，下个秋季不上课，下个春季上cs456，下个秋季上完cs789就可以毕业。
在本题中，只有两种学期，春季和秋季，每个新生的第一个学期总是秋季。
为了保证教学，大学限制每个学生每个学期最多可修的课程数，在输入数据中会给出相关的数值。

#格式#
##输入格式##
输入包含多组数据，以-1 -1结束。
每组数据的第一行是两个整数n和m，n代表课程总数（1 ≤ n ≤ 12），m代表每学期最多可修的课程数（2 ≤ m ≤ 6）。
接下去的一行包含n个字符串，分别表示n门课程的名称。
最后有n行分别给出n个课程的信息，每行表示一个课程，包括课程名（长度为1-5，包含字符{a-z, 0-9}），开课季度（F代表秋季，S代表春季，B代表每个季度都开课），该课程的前提课程数目p（0 ≤ p ≤ 5），最后p个是前提课程的课程名。

##输出格式##
输出按Sample Output的格式输出。

#样例1#
##样例输入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.

#限制#
1000ms
32768KB

#提示#

#来源#