University Course

A few years ago, Pinguinhos University introduced a new flexible credit system for incoming undergraduate students. Under the new system, students choose the courses they want to take in a semester. The only restriction is that a student cannot take a course A before taking every course that is set as a prerequisite of A. After a few semesters, the dean noticed that many students were failing many courses, simply because they were taking too many courses per semester. Some students enrolled in as many as fifteen courses in a single semester. Being very wise, this year the dean introduced an additional rule that limits the number of courses each student can take per semester to a fixed value $M$. This additional rule, however, left students very confused when choosing the courses to take each semester.

This is where you come into the story. The dean decided to provide a computer program to help students choose their courses, and asked for your help. More precisely, the dean wants the program to suggest the courses to take over the whole program as follows. Each course has a priority. If more than $M$ courses can be taken in a given semester (respecting the prerequisite system), the program suggests that the student enroll in the $M$ courses with the highest priority. If $M$ or fewer courses can be taken in a given semester, the program suggests that the student enroll in all available courses.

Given the prerequisites of each course, the priority of each course, and the maximum number of courses per semester, your program must compute the number of semesters needed to graduate by following the dean's suggestion, and the list of courses the student takes in each semester.

The input contains several test cases. A course with no prerequisite is called basic; otherwise it is called advanced.

The first line of a test case contains two integers $N$ and $M$ ($1 \le N \le 100$, $1 \le M \le 10$): the number of advanced courses and the maximum number of courses that can be taken per semester. Each of the next $N$ lines has the format

STR0 K STR1 STR2 ... STRK

where STR0 is the name of an advanced course, $K$ ($1 \le K \le 15$) is the number of prerequisites of STR0, and STR1, STR2, ..., STRK are the names of the prerequisites of STR0. A course name is a string of one to seven uppercase alphanumeric characters (A to Z and 0 to 9). Note that basic courses are those that appear only as a prerequisite of some advanced course. To graduate, a student must take (and pass) every basic and every advanced course.

The priority of the courses is the order in which they first appear in the input: the course that appears first has the highest priority, and the course that appears last has the lowest priority. The prerequisites contain no cycle (that is, if course B has course A as a prerequisite, then A does not have B as a prerequisite, directly or indirectly). The total number of courses in a test case is at most 200.

The end of the input is marked by a line with $N = M = 0$.

For each test case, print the output in the following form. The first line is Formatura em S semestres, where $S$ is the number of semesters needed to graduate by following the dean's suggestion. Each of the next $S$ lines describes the courses taken in one semester, one semester per line: Semestre i : followed by the course names separated by spaces, as in the sample output. Within each semester, list the courses in lexicographic order.

Definition: consider the strings $S_a = a_1a_2 \ldots a_m$ and $S_b = b_1b_2 \ldots b_n$. $S_a$ precedes $S_b$ in lexicographic order if and only if $S_b$ is non-empty and one of the following conditions holds:

• $S_a$ is the empty string.
• $a_1 < b_1$ in the order 0 < 1 < 2 < ... < 9 < A < B < ... < Z.
• $a_1 = b_1$ and $a_2a_3 \ldots a_m$ precedes $b_2b_3 \ldots b_n$.