题目描述

匈牙利数学家保罗·埃尔德什（Paul Erdős，1913-1996，发音为“Ar-dish”）不仅是$20$世纪最古怪的数学家之一，也是最著名的数学家之一。他直到高龄仍在发表广泛传播的论文，而任何有幸成为埃尔德什合著者的数学家都备受尊敬。

并非所有人都有机会与埃尔德什合著论文，因此许多人满足于与那些曾与埃尔德什合著过论文的人合作发表论文。这催生了所谓的埃尔德什数（Erdős number）：
• 与埃尔德什合著过论文的作者，其埃尔德什数为$1$。
• 未与埃尔德什合著但曾与埃尔德什数为$1$的人合著过的作者，其埃尔德什数为$2$，以此类推。

如今，几乎每个人都想知道自己的埃尔德什数是多少。你的任务是编写一个程序，计算给定科学家列表的埃尔德什数。

输入格式

输入文件包含多个测试用例，每个用例由一个论文数据库和一个名字列表组成。
• 每个用例以一行p n开始，其中$p$和$n$是自然数（$1 \leq p \leq 32000$，$1 \leq n \leq 3000$）。
• 接下来的$p$行是论文数据库，每行描述一篇论文，格式如下：

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

名字和标题可能包含ASCII码$32$到$126$的字符（逗号和冒号除外）。每个逗号后严格有一个空格。名字可能缩写，但同一名字的写法始终一致。特别地，埃尔德什的名字始终写作Erdos, P.。
• 随后是$n$行，每行包含一个名字（格式与论文数据库一致）。
• 输入以0 0结束。

约束条件：
• 每个名字不超过$40$个字符。
• 每行输入不超过$250$个字符。
• 每个用例中不同作者的数量不超过$10000$。

输出格式

对于每个测试用例：

1. 首先输出用例编号，格式为Database #k（$k$从$1$开始）。
2. 按输入顺序输出每个名字及其埃尔德什数。若某人与埃尔德什无关联，则输出infinity。
3. 每个用例后输出一个空行。

注意：输入规模较大，建议使用scanf。

输入样例 1

2 2
Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factors matrices.
Gardner, M., Martin, G.: Commuting Names
Smith, M.N.
Gardner, M.
0 0

输出样例 1

Database #1
Smith, M.N.: 1
Gardner, M.: 2

提示

• 埃尔德什数的计算规则：
• 若直接与Erdos, P.合著，则值为$1$。
• 若与埃尔德什数为$k$的人合著，则值为$k+1$。
• 样例解释：
• Smith, M.N.与埃尔德什合著，故其值为$1$。
• Gardner, M.未直接与埃尔德什合著，但与Martin, G.（埃尔德什数为$1$）合著，故其值为$2$。

来源

$2000$年中欧地区竞赛（Mid-Central European Regional Contest）