대학 교육과정

몇 년 전 핑기뉴스 대학교는 학부 신입생을 위한 새로운 유연 학점제를 도입했다. 이 제도에서 학생은 한 학기에 들을 과목을 자유롭게 고른다. 단 하나의 제약은 과목 A를 듣기 전에 A의 선수 과목으로 정해진 과목을 모두 먼저 들어야 한다는 것이다. 몇 학기가 지나자 총장은 많은 학생이 여러 과목에서 낙제한다는 사실을 알아차렸다. 학생들이 한 학기에 너무 많은 과목을 들었기 때문이다. 어떤 학생은 한 학기에 열다섯 과목까지 수강 신청했다. 현명한 총장은 올해 규칙을 하나 더 만들어 학생 한 명이 한 학기에 들을 수 있는 과목 수를 정해진 값 $M$ 이하로 제한했다. 그런데 이 규칙 때문에 학생들은 학기마다 어떤 과목을 들어야 할지 몹시 혼란스러워했다.

여기서 여러분이 등장한다. 총장은 학생들의 과목 선택을 돕는 프로그램을 제공하기로 했고, 여러분에게 도움을 요청했다. 프로그램은 졸업할 때까지 들을 과목을 다음 방식으로 제안해야 한다. 과목마다 우선순위가 있다. 어떤 학기에 (선수 과목 규칙을 지키면서) 들을 수 있는 과목이 $M$개보다 많으면, 프로그램은 우선순위가 가장 높은 $M$개 과목을 수강하라고 제안한다. 들을 수 있는 과목이 $M$개 이하이면 그 과목을 모두 수강하라고 제안한다.

각 과목의 선수 과목 정보, 과목별 우선순위, 학기당 최대 과목 수가 주어질 때, 총장의 제안을 따를 경우 졸업에 필요한 학기 수와 학기마다 수강할 과목 목록을 구하는 프로그램을 작성하시오.

입력은 여러 테스트 케이스로 이루어진다. 선수 과목이 하나도 없는 과목을 기초 과목, 그렇지 않은 과목을 심화 과목이라고 한다.

각 테스트 케이스의 첫 줄에는 두 정수 $N$과 $M$ ($1 \le N \le 100$, $1 \le M \le 10$)이 주어진다. $N$은 심화 과목의 수이고 $M$은 한 학기에 들을 수 있는 최대 과목 수이다. 다음 $N$개 줄은 각각 다음 형식이다.

STR0 K STR1 STR2 ... STRK

STR0은 심화 과목의 이름이고, $K$ ($1 \le K \le 15$)는 STR0의 선수 과목 수이며, STR1, STR2, ..., STRK는 STR0의 선수 과목 이름이다. 과목 이름은 영어 대문자(A부터 Z)와 숫자(0부터 9)로 이루어진 1자 이상 7자 이하의 문자열이다. 기초 과목은 어떤 심화 과목의 선수 과목으로만 등장한다는 점에 유의하라. 졸업하려면 기초 과목과 심화 과목을 모두 수강해서 통과해야 한다.

과목의 우선순위는 입력에 처음 등장하는 순서로 정한다. 가장 먼저 등장한 과목의 우선순위가 가장 높고, 가장 나중에 등장한 과목의 우선순위가 가장 낮다. 선수 과목 관계에는 순환이 없다. 즉 과목 B의 선수 과목이 A이면 A는 직접으로든 간접으로든 B를 선수 과목으로 두지 않는다. 한 테스트 케이스의 전체 과목 수는 최대 200이다.

입력의 끝은 $N = M = 0$인 줄로 나타낸다.

각 테스트 케이스마다 다음 형식으로 출력한다. 첫 줄에는 Formatura em S semestres를 출력한다. 여기서 $S$는 총장의 제안을 따를 때 졸업에 필요한 학기 수이다. 다음 $S$개 줄에는 학기마다 수강할 과목을 한 줄에 한 학기씩 Semestre i : 뒤에 과목 이름을 공백으로 구분해 출력한다. 형식은 예제 출력과 같다. 각 학기의 과목 목록은 사전순으로 정렬한다.

사전순의 정의는 다음과 같다. 문자열 $S_a = a_1a_2 \ldots a_m$과 $S_b = b_1b_2 \ldots b_n$이 있을 때, $S_b$가 비어 있지 않고 다음 조건 중 하나를 만족하면, 그리고 그때에만 $S_a$가 $S_b$보다 사전순으로 앞선다.

• $S_a$가 빈 문자열이다.
• 문자 순서 0 < 1 < 2 < ... < 9 < A < B < ... < Z에서 $a_1 < b_1$이다.
• $a_1 = b_1$이고 $a_2a_3 \ldots a_m$이 $b_2b_3 \ldots b_n$보다 사전순으로 앞선다.