Kevin Norwood Bacon (born July 8, 1958) is an American film and theater actor whose notable roles include Animal House, Diner, Footloose, Flatliners, Wild Things, A Few Good Men, Apollo 13, Mystic River, The Woodsman, Trapped, Friday the 13th, Hollow Man, Tremors, Death Sentence, Frost/Nixon, Crazy, Stupid, Love and X-Men: First Class.
Bacon has won Golden Globe and Screen Actors Guild Awards, was nominated for an Emmy Award, and was named by The Guardian as one of the best actors never to have received an Academy Award nomination.
In 2003, Bacon received a star on the Hollywood Walk of Fame.
He was good at playing various roles, and every actor or actress having the honor of being a partner to Bacon is well respected.
Not everybody got a chance to be a partner with Bacon, so many people were content if they managed to play a movie with somebody who had played a movie with Bacon. This gave rise to the so-called Bacon numbers. Nowadays, an advanced Bacon numbers have been invented, it also refer to the box office, when box office is larger, the number k is smaller. For example, An actor who has play in a movie with Bacon, with the number about this movie is k, had advanced Bacon number k. An actor who had not played with Bacon but with somebody(the movie they played together has a number k2) with Bacon number k1 obtained Bacon number k1+k2, and so on. Today, nearly every actor wants to know what the smallest advanced Bacon number he or she has. Your task is to write a program that computes advanced Bacon numbers for a given set of actor.
Input
The input file contains a sequence of actors, each scenario consisting of a movie 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.1 <= k <= 100 000. Following this line are p lines containing descriptions of movies (this is the movie database). A movie is played by a line of the following form:
k LastName1, FirstName1, LastName2, Firstname2, . . . : TitleOfTheMovie
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.
Example:
John, Belushi, Karen, Allen, Kevin, Bacon: Animal House
After the p movies follow n lines each containing exactly one name in the same format as in the movie 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 1100 different actors.
Output
For every scenario first print the number of the scenario in the format shown in the sample output. Then print for every actor name in the list of names their advanced Bacon number based on the movies in the movie database of the scenario. The actors should be output in the order given in the input file. Actors that do not have any relation to Bacon via the movies have advanced Bacon number infinity. Adhere to the format shown in the sample output.
Print a blank line after each case.
Sample Input
3 3
3 John, Belushi, Karen, Allen, Kevin, Bacon: Animal House
2 Tom, Hulce, Karen, Allen: Starting Over
1 Hill, Ken, Bob, Stock: kick the ball
John, Belushi
Tom, Hulce
Bob, Stock
0 0
Sample Output
Database 1
John, Belushi: 3
Tom, Hulce: 5
Bob, Stock: infinity
