beecrowd | 2249

Número de Erdos

Por OBI - Olimpíada Brasileira de Informática 2003 BR Brazil

Timelimit: 1

O matemático húngaro Paul Erdos (1913-1996), um dos mais brilhantes do século XX, é considerado o mais prolífico matemático da história. Erdos publicou mais de 1500 artigos, em colabora- ção com cerca de outros 450 matemáticos. Em homenagem a este gênio húngaro, os matemáticos criaram um número, denominado "número de Erdos". Toda pessoa que escreveu um artigo com Erdos tem o número 1. Todos que não possuem número 1, mas escreveram algum artigo juntamente com alguém que possui número 1, possuem número 2. E assim por diante. Quando nenhuma ligação pode ser estabelecida entre Erdos e uma pessoa, diz-se que esta possui número de Erdos infinito. Por exemplo, o número de Erdos de Albert Einstein é 2. E, talvez surpreendentemente, o número de Erdos de Bill Gates é 4.

Sua tarefa é escrever um programa que, a partir de uma lista de autores de artigos, determine o número de Erdos dos autores.

Entrada

A entrada é constituída por vários conjuntos de teste. A primeira linha de um conjunto de teste contém um número inteiro A (1 ≤ A ≤ 100), que indica o número de artigos. Cada uma das A linhas seguintes contém a lista de autores de um artigo. Cada autor é identificado pela inicial de seu nome (em maiúscula), seguida de um ponto e de um espaço em branco (indicando que o nome está abreviado), seguida de seu último sobrenome (‘P. Erdos’, por exemplo). O sobrenome de um autor possui, no máximo, 15 letras, e apenas a letra inicial aparece em maiúscula. Os autores são separados por vírgulas, e a lista de autores de um artigo termina com um ponto (veja os exem- plos abaixo). Um único espaço em branco separa a abreviatura do nome do sobrenome, bem como o nome de um autor do anterior. Espaços em branco não são usados em outros locais. Um artigo possui, no máximo, 10 autores, e o total de autores não excede 100. O final da entrada é indicado por A = 0.

Saída

Para cada conjunto de teste da entrada seu programa deve produzir um conjunto de linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato “Teste n”, onde n é numerado seqüencialmente a partir de 1. A seguir devem aparecer uma linha para cada autor do conjunto de testes (exceto o próprio P. Erdos). Cada linha deve conter o nome do autor seguido pelo caractere ‘:’, um espaço em branco e o seu número de Erdos. Caso o número de Erdos de um determinado autor seja infinito, escreva ‘infinito’. A saída deve ser ordenada alfabeticamente pelo sobrenome do autor, e, em caso de mesmo sobrenome, o desempate deve ser feito pela inicial do primeiro nome. Imprima uma linha em branco ao final de cada conjunto de teste. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo de Entrada Exemplo de Saída

5

P. Erdos, A. Selberg.

P. Erdos, J. Silva, M. Souza.

M. Souza, A. Selberg, A. Oliveira.

J. Ninguem, M. Ninguem.

P. Duarte, A. Oliveira.

2

Z. Silva, P. Erdos.

Z. Souza.

0

Teste 1

P. Duarte: 3

J. Ninguem: infinito

M. Ninguem: infinito

A. Oliveira: 2

A. Selberg: 1

J. Silva: 1

M. Souza: 1


Teste 2

Z. Silva: 1

Z. Souza: infinito