Time to Graduate

A prospective computer-science student wants to know how many semesters it will take to graduate from several different universities. Each university publishes a list of required courses, the prerequisites of each course, and the semesters in which each course is offered. Given this information, determine the minimum number of semesters needed to complete every required course.

Consider the following example. A student must take 4 courses: mt42, cs123, cs456, and cs789. mt42 is offered only in the fall and has no prerequisites. cs123 is offered only in the spring and has no prerequisites. cs456 is offered only in the spring and requires both cs123 and mt42. Finally, cs789 is offered in both fall and spring and requires cs456. The shortest time to graduate is 5 semesters: take mt42 in the fall, cs123 the following spring, cs456 the next spring (it is not offered in the fall), and cs789 the following fall.

There are only two kinds of semesters, fall and spring, and they alternate. Always start counting from a fall semester (semester 1 is fall, semester 2 is spring, semester 3 is fall, and so on).

In addition to the fall/spring scheduling, each university caps how many courses may be taken in a single semester in order to keep the dormitories full; this cap is part of the input. A course may be taken in a given semester only if it is offered that semester, all of its prerequisites were completed in earlier semesters, and the semester's course cap is not exceeded.

The input contains from one to twenty-five data sets, followed by a final line containing only the two integers -1 -1.

Each data set begins with a line containing two positive integers n and m, where n ($1 \le n \le 12$) is the number of courses in the data set and m ($2 \le m \le 6$) is the maximum number of courses that may be taken in any single semester.

The next line contains the n course identifiers. Each identifier is a string of 1 to 5 characters drawn from {a-z, 0-9}.

The course identifiers are followed by n lines of course information, one per course. Each such line contains the course identifier, the semester it is offered ('F' = fall, 'S' = spring, 'B' = both semesters), the number of prerequisite courses p ($0 \le p \le 5$), and then the p prerequisite course identifiers.

For each data set, print a single line in exactly the following format:

The minimum number of semesters required to graduate is X.

where X is the minimum number of semesters required to complete all of the required courses.