Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NUMERDOS - Número de Erdos

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.

Tarefa

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 exemplos 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

Entrada:
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

Saída
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

Restrições

0 <= A <= 100 (número de artigos de um caso de teste; A = 0 apenas para indicar final da entrada)
1 <= tamanho, em número de letras, do sobrenome de um autor <= 15
1 <= número de autores de um artigo <= 10
1 <= número total de autores em um conjunto de teste <= 100


Adicionado por:Wanderley Guimarăes
Data:2006-05-05
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL VB.NET
Origem:Olimpiada Brasileira de Informatica 2003

hide comments
2016-04-17 05:33:00 Elsio [UFABC]
Passou tranquilo com um grafo simples, usando map pra transformar string em numero e Floyd Warshall pra pegar as distâncias.
Ótimo exercício sobre grafos e input de strings.
2014-11-27 21:51:34 skiesoff
Input mais complicado que o próprio exercício... legal.
2014-07-19 21:20:48 Tiago Nápoli
Lembrem-se que o P. Erdos pode năo aparecer nos artigos... me segurou bastante esse detalhe.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.