Erdös Numbers

The Hungarian mathematician Paul Erdös (1913–1996, pronounced "Ar-dish") was one of the most prolific and most famous mathematicians of the 20th century. He kept publishing widely circulated papers into very old age, and every mathematician who had the honor of being a co-author of Erdös is well respected.

Not everybody got the chance to co-author a paper with Erdös, so many people were content to publish a paper with somebody who had published a paper with 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 has published with somebody of Erdös number 1 has Erdös number 2, and so on. Erdös himself has Erdös number 0.

Given a database of papers and a list of author names, compute the Erdös number of each queried author.

The input contains a sequence of scenarios. Each scenario consists of a paper database and a list of names.

A scenario begins with a line "p n", where $p$ and $n$ are natural numbers with $1 \le p \le 32000$ and $1 \le n \le 3000$.

The next $p$ lines describe the papers (the paper database). Each paper is described by a single line of the form:

LastName1, FirstName1, LastName2, FirstName2, ...: TitleOfThePaper

The names and the title may contain any ASCII character from 32 to 126 except commas and colons. Exactly one space follows each comma. A first name may be abbreviated, but the same name is always written the same way. In particular, Erdös's name is always written as "Erdos, P." (umlauts such as 'ö', 'ä', ... are written simply as 'o', 'a', ...).

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 is longer than 40 characters. No input line is longer than 250 characters. Each scenario has at most 10000 different authors.

For every scenario, first print a line "Database #k", where $k$ is the number of the scenario (starting from 1). Then, for every queried name, print a line "name: e", where $e$ is that author's Erdös number based on the papers of the scenario. Print the authors in the order they are given in the input. An author who has no connection to Erdös through the papers has Erdös number "infinity"; print the word "infinity" for that author.