SPOJ Brasil

Há alguns anos atrás, a Universidade de Pinguinhos introduziu um novo sistema flexível de créditos para os alunos ingressantes de cursos de graduação. No novo sistema os alunos podem escolher as disciplinas que desejam cursar em um semestre, com a unica restrição de não poderem cursar uma dada disciplina A sem antes terem cursado todas as disciplinas que tiverem sido estabelecidas como pré-requisitos de A. Após alguns semestres o reitor notou que muitos estudantes estavam sendo reprovados em muitas disciplinas, simplesmente porque os estudantes estavam cursando muitas disciplinas por semestre – alguns estudantes chegavam a se matricular em até quinze disciplinas em um semestre. Sendo muito sábio, este ano o reitor introduziu uma regra adicional limitando o número de disciplinas que cada estudante pode cursar por semestre a um certo valor N . Essa regra adicional, no entanto, fez com que os alunos ficassem muito confusos na hora de escolher as disciplinas a serem cursadas em cada semestre.

E aí que você entra na estória. O reitor resolveu disponibilizar um programa de computador para ajudar os alunos a fazerem suas escolhas de disciplinas, e solicitou sua ajuda. Mais precisamente, o reitor quer que o programa sugira as disciplinas a serem cursadas durante o curso da seguinte forma. A cada disciplina é atribuída uma prioridade. Se mais do que N disciplinas podem ser cursadas em um determinado semestre (obedecendo ao sistema de pré-requisitos), o programa deve sugerir que o aluno matricule-se nas N disciplinas de maior prioridade. Se N ou menos disciplinas podem ser cursadas em um determinado semestre, o programa deve sugerir que o aluno matricule-se em todas as disciplinas disponíveis.

Portanto, dadas a descrição de pré-requisitos para cada disciplina, a prioridade de cada disciplina, e o número máximo de disciplinas por semestre, seu programa deve calcular o número necessário de semestres para concluir o curso, segundo a sugestão do reitor, e a lista de disciplinas que o aluno deve matricular-se em cada semestre.

Entrada

A entrada contém vários casos de teste. Se uma disciplina não tem qualquer pré-requisito ela é denominada básica; caso contrário ela é denominada avançada. A primeira linha de um caso de teste contém dois inteiros 1 <= N <= 100 e 1 <= M <= 10 indicando respectivamente o número de disciplinas avançadas do curso e o número máximo de disciplinas que podem ser cursadas por semestre. Cada uma das N linhas seguintes tem o formato

STR0 K STR1 STR2 ... STRK

onde STR0 é o nome de uma disciplina avançada, 1 <= K <= 15 é o número de disciplinas que são pré-requisitos de STR0, e STR1, STR2, . . . STRK são os nomes das disciplinas que são pré-requisitos de STR0. O nome de uma disciplina é uma cadeia com no mínimo um e no máximo sete caracteres alfanuméricos maiúsculos (‘A’-‘Z’ e ‘0’-‘9’). Note que as disciplinas básicas são aquelas que aparecem apenas como pré-requisito de alguma disciplina avançada. Para concluir o curso, um aluno deve cursar (e passar!) todas as disciplinas básicas e avançadas. A prioridade das disciplinas é determinada pela ordem em que elas aparecem pela primeira vez na entrada: a que aparece primeiro tem maior prioridade, e a que aparece por último tem a menor prioridade. Não há circularidade nos pré-requisitos (ou seja, se a disciplina B tem como pré-requisito a disciplina A então A não tem B como pré-requisito, direta ou indiretamente). O número total de disciplinas é no máximo igual a 200. O final da entrada é indicado por N = M = 0.

Saída

Para cada caso de teste da entrada seu programa deve produzir a saída na seguinte forma. A primeira linha deve conter a frase ‘Formatura em S semestres’, onde S é o número de semestres necessários para concluir o curso segundo a sugestão do reitor. As S linhas seguintes devem conter a descrição das disciplinas a serem cursadas em cada semestre, um semestre por linha, no formato mostrado no exemplo de saída abaixo. Para cada semestre, a lista das disciplinas deve ser dada em ordem lexicográfica.

Definição: considere as cadeias de caracteres S_a = a₁ a₂ ...a_m e S_b = b₁ b₂ . . . b_n . S_a precede S_b em ordem lexicográfica se e apenas se S_b é não-vazia e uma das seguintes condições é verdadeira: • S_a é uma cadeia vazia; • a₁ < b₁ na ordem ‘0 < ‘1 < ‘2 < . . . < ‘9 < ‘A < ‘B < . . . < ‘Z ; • a₁ = b₁ e a cadeia a₂ a₃ . . . a_m precede a cadeia b₂ b₃ . . . b_n.

Exemplo de entrada

2 2
B02 3 A01 A02 A03
C01 2 B02 B01
3 2
ARTE2 1 ARTE1
PROG3 1 PROG2
PROG2 2 MAT1 PROG1
0 0

Saída para o exemplo de entrada

Formatura em 4 semestres
Semestre 1 : A01 A02
Semestre 2 : A03 B01
Semestre 3 : B02
Semestre 4 : C01
Formatura em 4 semestres
Semestre 1 : ARTE1 MAT1
Semestre 2 : ARTE2 PROG1
Semestre 3 : PROG2
Semestre 4 : PROG3