Erdos Numbers
Time Limit: 10 Seconds Memory Limit: 32768 KB
The Hungarian Paul Erdos (1913C1996, pronounced as Ar-dish) was not only
one of the strangest mathematicians of the 20th century, he was also among the
most famous ones. He kept on publishing widely circulated papers up to a very
high age, and every mathematician having the honor of being a co-author to Erdos
is well respected.
Not everybody got a chance to co-author a paper with Erdos, so many people were
content if they managed to publish a paper with somebody who had published a
paper with Erdos. This gave rise to the so-called Erdos numbers. An author who
has jointly published with Erdos had Erdos number 1. An author who had not published
with Erdos but with somebody with Erdos number 1 obtained Erdos number 2, and
so on. Today, nearly everybody wants to know what Erdos number he or she has.
Your task is to write a program that computes Erdos numbers for a given set
of scientists.
Input
The input file contains a sequence of scenarios, each scenario consisting of
a paper database and a list of names. A scenario begins with the line p n,
where p and n are natural numbers with 1<=p<=32000;1<=n<=3000. Following
this line are p lines containing descriptions of papers (this is the paper database).
A paper is described by a line of the following form:
LastName1, FirstName1, LastName2, Firstname2, . . . : TitleOfThePaper
The names and the title may contain any ASCII characters between 32 and 126
except commas and colons. There will always be exactly one space character following
each comma. The first name may be abbreviated, but the same name will always
be written in the same way. In particular, Erdos name is always written as
Erdos, P.. (Umlauts like o,a,. . . are simply written as o,a, .
. . .)
Example:
Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factors matrices.
After the p papers follow n lines each containing exactly one name in the same
format as in the paper database.
The line 0 0 terminates the input.
No name will consist of more than 40 characters. No line in the input file contains
more than 250 characters. In each scenario there will be at most 10 000 different
authors.
Output
For every scenario first print the number of the scenario in the format shown
in the sample output. Then print for every author name in the list of names
their Erdos number based on the papers in the paper database of the scenario.
The authors should be output in the order given in the input file. Authors that
do not have any relation to Erdos via the papers have Erdos number infinity. Adhere
to the format shown in the sample output.
Print a blank line after each case.
Sample Input
2 2 Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factors matrices. Gardner, M., Martin, G.: Commuting Names Smith, M.N. Gardner, M. 0 0
Sample Output
Database #1 Smith, M.N.: 1 Gardner, M.: 2Submit
Source: Mid-Central European Regional Contest 2000