에르되시 수

학계에는 저명한 수학자 폴 에르되시(Paul Erdős)의 이름을 딴 에르되시 수라는 개념이 있습니다. 어떤 사람의 에르되시 수는 다음 규칙으로 정해지는 값들 중 가장 작은 값입니다.

• 에르되시의 에르되시 수는 0입니다.
• 에르되시와 함께 논문을 쓴 사람의 에르되시 수는 1입니다.
• 에르되시 수가 1인 사람과 함께 논문을 쓴 사람의 에르되시 수는 2이고, 이런 식으로 계속됩니다.

위 규칙 중 어느 것도 적용되지 않으면 에르되시 수는 무한대입니다. 에르되시 수가 작을수록 에르되시와의 공동 저술 관계가 더 가깝다는 뜻입니다.

그런데 이 고전적인 정의는 시간의 흐름을 고려하지 않습니다. 예를 들어 에르되시가 A와 논문을 쓰고, A가 B와 논문을 썼다고 합시다. 그러면 A는 1, B는 2를 받습니다. 하지만 A가 B와 쓴 논문은 경력 초기에, 에르되시와 쓴 논문은 훨씬 나중에 나왔을 수도 있습니다. 이런 경우에도 B가 이미 2를 갖는 것이 타당할까요? 고전적 정의는 단지 에르되시와 어떤 사람을 잇는 가장 짧은 논문 사슬의 길이만을 셉니다.

시간의 영향을 반영하기 위해 다음 조건을 추가합니다. 에르되시에서 출발하는 사슬에 등장하는 논문들의 출판 연도는 반드시 강한 증가 수열(순증가)을 이루어야 합니다. 즉, 사슬에서 다음 논문은 항상 이전 논문보다 엄격히 더 늦은 연도에 출판되어야 합니다.

주어진 논문 목록에 대해, 위 조건을 적용했을 때 "특정 연도를 기준으로 특정 사람의 에르되시 수는 얼마인가?"라는 질문에 답해야 합니다. 어떤 사람의 연도 $Y$ 기준 에르되시 수는, $Y$년 이하에 출판된 논문만 사용하고 연도가 순증가하는, 에르되시에서 그 사람까지의 가장 짧은 유효한 사슬의 길이(논문 개수)입니다. 그런 사슬이 없으면 답은 무한대입니다.

첫 번째 줄에 이어지는 데이터 집합의 개수 $z$가 주어집니다.

각 데이터 집합의 형식은 다음과 같습니다.

• 첫 줄에 두 정수 $p$와 $q$가 주어집니다 ($1 \le p, q \le 100000$). 각각 논문의 수와 질문의 수입니다.
• 이어지는 $p$개의 줄은 각각 하나의 논문을 나타냅니다. 한 줄에는 출판 연도 $y$ ($1913 \le y \le 2005$)가 먼저 나오고, 그 뒤에 공백으로 구분된 (서로 다른) 모든 공동 저자의 성이 나옵니다. 각 논문의 저자 수는 $2$명 이상 $10$명 이하입니다. 성은 영문자로 이루어진 문자열로, 첫 글자는 대문자이고 나머지는 소문자이며 길이는 $1$자 이상 $10$자 이하입니다.
• 이어지는 $q$개의 줄은 각각 하나의 질문을 나타냅니다. 한 줄에는 질문하는 연도 $y$가 먼저 나오고, 공백 뒤에 한 사람의 성이 나옵니다(성의 형식은 위와 같습니다).

한 데이터 집합에 등장하는 서로 다른 저자의 수는 $100000$을 넘지 않습니다. 폴 에르되시는 입력에서 성 Erdos로 표기됩니다.

각 데이터 집합에 대해 질문 순서대로 $q$개의 줄을 출력합니다. 각 질문에 대해, 질문한 연도를 기준으로 한 해당 인물의 에르되시 수를 출력합니다. 그 에르되시 수가 무한대이면 NIESKONCZONA("무한"을 뜻하는 폴란드어)를 출력합니다.