Erdös 수

수학자 Paul Erdös는 여러 가지로 알려져 있는데, 그중 하나는 가장 많은 수학 출판물을 쓴 수학자라는 것이다 (하지만 Leonhard Euler는 쓴 페이지 수가 가장 많다). Erdös는 출판물을 쓸 때 매우 활발하게 공동 작업을 했다. 인용되지 않은 출처에 따르면 그는 종종 동료의 집에서 임시로 지냈다고 한다. 방문하는 동안 그는 그 동료와 함께 출판물을 썼고, 더 이상 환대를 받을 수 없게 되면 다음 동료에게로 옮겨 갔다.

Erdös와 함께 출판물을 썼다는 것은 큰 명예로 여겨진다. Erdös와 함께 출판물을 쓴 사람은 Erdös 수가 1인 것으로 정의한다. Erdös 수가 1인 사람과 함께 출판물을 썼다면 Erdös 수는 2이 되며, 이런 식으로 계속된다.

출판물 목록이 주어질 때, 관련된 모든 수학자의 Erdös 수를 목록으로 출력한다.

점수

제출한 해답은 여러 테스트 케이스 그룹으로 채점된다. 한 그룹에서 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$40$| $M \leq 5000$

$2$ |$60$| 추가 제한 없음.

첫 번째 줄에는 두 정수 $N$과 $M$이 주어진다 ($1 \le N \le 5\,000$, $1 \le M \le 40\,000$). 이들은 각각 수학자의 수와 출판물의 수이다.

이어서 각각 하나의 출판물을 설명하는 $M$개의 줄이 주어진다. 각 줄은 해당 출판물에서 공동 작업한 수학자의 수를 나타내는 정수로 시작한다. 그 뒤에 수학자들의 이름이 공백으로 구분되어 주어지며, 수학자들의 순서는 중요하지 않다. 수학자의 이름은 1개 이상 20개 이하의 대문자 $A - Z$로 이루어진다. 서로 다른 두 수학자가 같은 이름을 갖는 경우는 없다. Erdös의 이름은 ERDOS이다. 각 출판물에는 적어도 2명, 최대 5명의 수학자가 참여한다. 관련된 모든 수학자의 Erdös 수는 유한하다고 가정할 수 있다.

수학자와 그들의 Erdös 수를 한 줄에 하나씩 목록으로 출력한다. ERDOS도 이 목록에 포함되어야 하며, 그의 Erdös 수는 항상 0이다. 목록은 알파벳 순으로 정렬해야 한다.