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öshas a humongous amount of street credibility among mathematicians (and thus pretty much none among everyone else).

Of course, not everyone got a chance to publish a paper with Erdös. The best they could do was publish a paper with one of the co-authors of Erdös. This gave rise to the so-called Erdös numbers. An author who has jointly published with Erdös has Erdös number 1. An author who has not published with Erdös but with someone with Erdös number 1 has 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 first line contains the number of scenarios. Each scenario consists of a paper database and a list of names. It begins with the line \(P \; N\), where \(P\) and \(N\) are natural numbers. Following this line is the paper database, with \(P\) lines each consisting of the description of one paper specified in the following way:

Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factors

Note that umlauts, such as "ö", are simply written as "o". After the \(P\) papers follow \(N\) lines with names. A name line has the following format:

Martin, G.


For every scenario, you are to print a line containing a string "Scenario i" (where \(i\) is the number of the scenario starting at 1) and the author names together with their Erdös number of all authors in the list of names. The authors should appear in the same order as they appear in the list of names. The Erdös number is based on the papers in the paper database of this scenario. Authors which do not have any relation to Erdös via the papers in the database have Erdös number "infinity".

Sample Input

4 3
Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factors
Erdos, P., Reisig, W.: Stuttering in petri nets
Smith, M.N., Chen, X.: First order derivatives in structured programming
Jablonski, T., Hsueh, Z.: Selfstabalizing data structures
Smith, M.N.
Hsueh, Z.
Chen, X.

Sample Output

Scenario 1
Smith, M.N. 1
Hsueh, Z. infinity
Chen, X. 2

This is challenge 10044 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.


Difficulty (4 votes)
Average test runtime 0.17
Points (changes over time) 10
Tried by 5 users
Solved by 5 users

Global ranking

# Name Runtime Points worth
1 贝尔恩德 0.13 12
2 ,s/java/NaN/gi 0.13 12
3 Ali 0.15 10
4 Pascal 0.15 10
5 JB 0.31 5