# Kevin Bacon

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

• 写回答

#### 1条回答默认 最新

• threenewbee 2017-09-07 01:25
关注
本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论

#### 悬赏问题

• ¥15 请问代码技术们，云梦建站的这个坑你们踩过吗？
• ¥20 androidstudio工具问题
• ¥15 想问一些关于计量的问题
• ¥15 关于c++外部库文件宏的问题，求解
• ¥15 office打开卡退（新电脑重装office系统后）
• ¥300 FLUENT 火箭发动机燃烧EDC仿真
• ¥15 【Hadoop 问题】Hadoop编译所遇问题hadoop-common: make failed with error code 2
• ¥15 vb6.0+webbrowser无法加载某个网页求解
• ¥15 RPA财务机器人采购付款流程
• ¥15 计算机图形多边形及三次样条曲线绘制