시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 128 MB71120.000%

문제

W środowisku naukowców znane jest pojęcie liczby Erdösa od nazwiska słynnego matematyka. Możesz policzyć swoją liczbę Erdösa jako najmniejszą z liczb wyznaczonych w sposób następujący:

  • Erdös ma liczbę 0.
  • Jeśli napisałeś publikację z Erdösem, to otrzymujesz liczbę 1.
  • Jeśli napisałeś publikację z kimś kto ma liczbę 1, otrzymujesz liczbę 2, itd.

Gdy nie ma zastosowania żadna z powyższych reguł, to liczba Erdösa jest nieskończona. W założeniu im mniejsza wartość liczby Erdösa, tym wyższy poziom naukowy danej osoby. Łatwo jednak zauważyć, że taka definicja nie uwzględnia rozwoju naukowców w czasie. Przykładowo jeśli Erdös napisał pracę z A, natomiast A napisał z B, to A otrzymuje liczbę 1, a B liczbę 2. Mogło się jednak zdarzyć, że A napisał pracę z B na początku swojej kariery, natomiast z Erdösem dużo później. Czy w tej sytuacji właściwie jest posiadanie liczby 2 przez B? W podanej definicji liczy się długość najkrótszego łańcucha publikacji łączącego daną osobę z Erd¨osem. Aby uwzględnić wpływ czasu wprowadzamy założenie, że daty publikacji w łańcuchu zaczynającym się od Erdösa muszą tworzyć ciąg silnie rosnący. Mając daną listę publikacji musisz odpowiedzieć na pytanie o liczbę Erdösa podanej osoby w podanym roku z uwzględnieniem powyższego założenia.

입력

Pierwsza linia wejścia zawiera małą liczbę całkowitą z – liczbę zestawów danych występujących kolejno po sobie. Opis jednego zestawu jest następujący:

Składa się on w pierwszej linii z dwóch liczb całkowitych p, q (1 ≤ p, q ≤ 100000) oznaczających odpowiednio liczbę publikacji i pytań. W kolejnych liniach znajduje się opis p publikacji. Opis publikacji składa się z jednej linii zawierającej y (1913 ≤ y ≤ 2005) oznaczającej rok publikacji oraz, po spacji, nazwiska (różnych) wszystkich współautorów rozdzielonych spacjami. Nazwisko jest ciągiem liter alfabetu angielskiego. Pierwsza litera jest wielka pozostałe małe. Długość wynosi od 1 do 10 znaków. Liczba autorów danej pracy wynosi od 2 do 10. W kolejnych q liniach znajdują się pytania. Opis pytania składa się z liczby y będącej rokiem o który pytamy oraz, po spacji, nazwiska osoby (ograniczenia jak wyżej). Liczba autorów w pliku nie przekracza 100000. Nazwisko Erdösa występuje w pliku jako Erdos.

출력

Dla każdego zestawu danych wypisz q linii stanowiących odpowiedzi na pytania z zestawu. Dla każdego pytania wypisz liczbę Erd¨osa podanej osoby w pytanym roku. Jeśli liczba Erdösa jest nieskończona wypisz NIESKONCZONA.

예제 입력 1

1
3 4
1943 Erdos Tarski
1929 Kuratowski Tarski
1971 Henkin Monk Tarski
1929 Kuratowski
1980 Monk
1929 Monk
1943 Tarski

예제 출력 1

NIESKONCZONA
2
NIESKONCZONA
1