에르되시 수

헝가리의 수학자 폴 에르되시(Paul Erdös, 1913–1996, "아르디시"로 발음)는 20세기의 가장 다작이면서도 가장 유명한 수학자 중 한 명이었다. 그는 아주 늦은 나이까지 널리 읽히는 논문을 계속 발표했고, 에르되시와 공저자가 되는 영광을 누린 수학자는 모두 큰 존경을 받는다.

모두가 에르되시와 함께 논문을 쓸 기회를 가진 것은 아니었기에, 많은 사람들은 에르되시와 함께 논문을 낸 적이 있는 누군가와 함께 논문을 내는 것으로 만족했다. 여기서 이른바 에르되시 수가 생겨났다. 에르되시와 공동으로 논문을 발표한 저자의 에르되시 수는 1이다. 에르되시와는 함께 발표한 적이 없지만 에르되시 수가 1인 사람과 함께 발표한 저자의 에르되시 수는 2이며, 이런 식으로 이어진다. 에르되시 자신의 에르되시 수는 0이다.

논문 데이터베이스와 저자 이름 목록이 주어질 때, 질의된 각 저자의 에르되시 수를 구하라.

입력은 여러 시나리오로 이루어진다. 각 시나리오는 하나의 논문 데이터베이스와 이름 목록으로 구성된다.

각 시나리오는 "p n" 형태의 줄로 시작하며, $p$와 $n$은 $1 \le p \le 32000$, $1 \le n \le 3000$을 만족하는 자연수이다.

이어지는 $p$개의 줄은 논문(논문 데이터베이스)을 설명한다. 각 논문은 다음 형태의 한 줄로 주어진다.

성1, 이름1, 성2, 이름2, ...: 논문제목

이름과 제목에는 쉼표와 콜론을 제외한 ASCII 32~126의 임의의 문자가 올 수 있다. 각 쉼표 뒤에는 정확히 하나의 공백이 온다. 이름은 축약될 수 있지만, 같은 이름은 항상 같은 방식으로 표기된다. 특히 에르되시의 이름은 항상 "Erdos, P."로 표기된다(움라우트 'ö', 'ä', ... 는 각각 'o', 'a', ... 로 단순 표기된다).

$p$개의 논문 다음에는 $n$개의 줄이 이어지며, 각 줄에는 논문 데이터베이스와 같은 형식의 이름이 정확히 하나씩 들어 있다.

"0 0" 줄이 입력의 끝을 나타낸다.

이름의 길이는 40자를 넘지 않는다. 입력의 어떤 줄도 250자를 넘지 않는다. 각 시나리오의 서로 다른 저자는 최대 10000명이다.

각 시나리오마다 먼저 "Database #k" 줄을 출력한다. 여기서 $k$는 시나리오 번호이며 1부터 시작한다. 그다음, 질의된 각 이름에 대해 "name: e" 줄을 출력한다. 여기서 $e$는 해당 시나리오의 논문들을 기준으로 계산한 그 저자의 에르되시 수이다. 저자는 입력에 주어진 순서대로 출력한다. 논문을 통해 에르되시와 아무런 연결도 없는 저자의 에르되시 수는 "infinity"이며, 그 저자에 대해서는 단어 "infinity"를 출력한다.