Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Forum Home ProblemSet Status Ranklist Contest LoginRegister Exam
Problem 1027. -- Erdös Numbers

Erdös Numbers

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 26  Solved: 1


The Hungarian Paul Erdös (1913-1996) was one of the most famous mathematicians of the 20th century. Every mathematician having the honor of being a co-author of Erdös is well respected. Unfortunately, not everybody got the chance to write a paper with Erdös, so the best they could do was publish a paper with somebody who had published a scientific paper with Erdös. This gave rise to the so-called Erdös numbers. An author who has jointly published with Erdös had Erdös number 1. An author who had not published with Erdös but with somebody with Erdös number 1 obtained Erdös number 2, and so on. Your task is to write a program which computes Erdös numbers for a given set of papers and scientists.


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.


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.: 2 




Mid-Central European Regional Contest 2000



한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin