Login:
Username:
Password:
Remember login

Create new account
110206

Erdös Numbers

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.

Input

The first line of the input 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 containing 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, like ``ö,'' are simply written as ``o''. After the P papers follow N lines with names. Such a name line has the following format: 

Martin, G.

Output

For every scenario you are to print a line containing a string ``Scenario i" (where i is the number of the scenario) 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 

1
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 derivates in structured programming
Jablonski, T., Hsueh, Z.: Selfstabilizing data structures
Smith, M.N.
Hsueh, Z.
Chen, X.

Sample Output 

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