졸업까지 걸리는 시간

컴퓨터공학과 진학을 준비하는 한 학생이 여러 대학에서 졸업까지 몇 학기가 걸리는지 알아보려고 한다. 각 대학은 이수해야 하는 필수 과목 목록, 각 과목의 선수 과목, 그리고 각 과목이 개설되는 학기를 알려 준다. 이 정보가 주어졌을 때, 모든 필수 과목을 이수하여 졸업하기까지 필요한 최소 학기 수를 구하여라.

다음 예를 보자. 어떤 학생이 mt42, cs123, cs456, cs789의 4개 과목을 들어야 한다. mt42는 가을 학기에만 개설되며 선수 과목이 없다. cs123은 봄 학기에만 개설되며 선수 과목이 없다. cs456은 봄 학기에만 개설되며 cs123과 mt42를 모두 선수 과목으로 요구한다. 마지막으로 cs789는 가을과 봄 두 학기 모두 개설되며 cs456을 선수 과목으로 요구한다. 이때 졸업까지 걸리는 가장 짧은 기간은 5학기이다. 가을에 mt42, 다음 봄에 cs123, 그 다음 봄에 cs456(가을에는 개설되지 않으므로), 마지막으로 그 다음 가을에 cs789를 들으면 된다.

학기는 가을과 봄 두 종류뿐이며 번갈아 나타난다. 학기는 항상 가을부터 세기 시작한다(1학기는 가을, 2학기는 봄, 3학기는 가을, ...).

가을/봄 개설 여부 외에 한 가지 제약이 더 있다. 각 대학은 기숙사를 가득 채우기 위해 한 학기에 들을 수 있는 과목 수를 제한하며, 이 제한값은 입력으로 주어진다. 어떤 과목을 특정 학기에 들으려면, 그 과목이 해당 학기에 개설되어 있고, 그 과목의 모든 선수 과목을 이전 학기에 이미 이수했으며, 그 학기의 수강 제한을 넘지 않아야 한다.

입력은 1개 이상 25개 이하의 데이터 세트로 이루어지며, 마지막에는 두 정수 -1 -1만 있는 줄이 온다.

각 데이터 세트는 두 양의 정수 n과 m이 있는 줄로 시작한다. n ($1 \le n \le 12$)은 해당 데이터 세트의 과목 수이고, m ($2 \le m \le 6$)은 한 학기에 들을 수 있는 최대 과목 수이다.

다음 줄에는 n개의 과목 식별자가 온다. 각 식별자는 {a-z, 0-9}로 이루어진 길이 1~5의 문자열이다.

그 뒤에는 각 과목의 정보가 한 줄에 하나씩 총 n줄 이어진다. 각 줄에는 과목 식별자, 개설 학기('F'=가을, 'S'=봄, 'B'=두 학기 모두), 선수 과목의 개수 p ($0 \le p \le 5$), 그리고 p개의 선수 과목 식별자가 차례로 주어진다.

각 데이터 세트마다 다음 형식과 정확히 일치하는 한 줄을 출력한다.

The minimum number of semesters required to graduate is X.

여기서 X는 모든 필수 과목을 이수하는 데 필요한 최소 학기 수이다.