AlgoLiga 2018

Nasze Ministerstwo Do Spraw Kolonizacji (MDSK) wyprzedza całą światową konkurencję! Podczas kiedy wszelkie mocarstwa planują stworzenie kolonii na Marsie czy księżycu nasze ministerstwo swymi planami obejmuje już Neptun. Plan ten jest genialny w swojej prostocie - zanim jakikolwiek inny kraj pomyśli o skolonizowaniu tej planety my już będziemy mieć gotowy schemat działania, co w efekcie pozwoli na pozostawienie konkurentów daleko w tyle. Jako wybitna jednostka analityczno-matematyczno-programistyczna zostałeś wyznaczony do stworzenia symulacji opisywanego przedsięwzięcia. Ministerstwo już od jakiegoś czasu skupia na owym planie wszelkie swoje wysiłki licząc na spektakularny sukces, tak więc niech nie dziwi Cię fakt, że scenariusz jest już mocno zaawansowany, oto on (nasze ministerstwo zakłada że):

• na Neptuna dotrze jednocześnie n mocarstw
• przedstawiciele każdego z nich trafią na miejsce idealne do założenia kolonii i natychmiast to zrobią
• po danym czasie m (może być on różny w zależności od mocarstwa) na miejscu założenia kolonii (każdej, nie tylko tej pierwszej) zabraknie miejsca na budowę nowych domów i koloniści rozejdą się do wszystkich wolnych miejsc nadających się do założenia kolonii, jakie połączone są bezpośrednio z ich obecnym miejscem
• schemat ten będzie powtarzał się aż do wyczerpania miejsc dogodnych do założenia nowej kolonii - wtedy najzwyczajniej w świecie za przykładem Chin wprowadzona zostanie kara śmierci za posiadanie kolejnego potomka i w ten prosty sposób populacja przestanie się rozrastać
• koloniści to wyjątkowo cywilizowani ludzie i nie toczą żadnych wojen a widząc zajęte już miejsce nawet nie próbują się do niego dostać

Znając już założenia odnośnie symulacji kolonizacji wspomóż ministerstwo i napisz program, który policzy czy w określonym momencie dane miejsce nadające się do założenia kolonii jest zajęte i jeżeli tak to przez jaki kraj. Prędko do dzieła, zanim ktokolwiek w MDSK zorientuje się że Neptun to gazowy olbrzym!

Wejście

W pierwszej linii wejścia znajdują się dwie liczby v oraz e (1 ≤ v ≤ 1600; 0 ≤ e ≤ 2100) określające odpowiednio ilość miejsc dogodnych do założenia kolonii oraz liczbę połączeń pomiędzy tymi miejscami. W kolejnych e liniach znajdują się opisy połączeń (zapis 0 1 oznacza, że miejsce numer 0 połączone jest z miejscem numer 1). W następnej, po opisie połączeń, linii znajduje się liczba n (1 ≤ n ≤ 40) określająca liczbę mocarstw jakie dotarły jednocześnie na Neptun. W dalszych n liniach znajdują się po dwie liczby - pierwsza to numer miejsca określającego miejsce początkowej kolonii, druga zaś to m (1 ≤ m ≤ 5000) opisująca po jakim czasie przedstawiciele n-tego mocarstwa wyruszą po nowe terytoria (n-te mocarstwo opisane zostało w n-tej linii). Druga część wejścia to opis zapytań. Składa się ona z q (1 ≤ q ≤ 1600) określającego ich liczbę oraz z q linii w których znajdują się owe zapytania. Każde z zapytań składa się z dwóch liczb a oraz b (0 ≤ a < v; b ≤ 5000), a określa miejsce o jakie pyta ministerstwo, b zaś to liczba kolejek po których sytuację należy przedstawić. Uznajemy, że mocarstwa poruszają się w kolejności zgodnej z kolejnością na wejściu.

Wyjście

Na wyjściu należy w oddzielnej linii dla każdego z q zapytań zwrócić numer mocarstwa jakie zamieszkuje miejsce a po b kolejkach lub znak "-" jeżeli żadne mocarstwo w momencie b nie przebywa w tym miejscu. Mocarstwa numerujemy od 1 zgodnie z kolejnością na wejściu.

Przykład

Wejście:

9 11
0 1
0 7
1 2
2 3
2 5
3 7
3 4
4 6
6 5
5 7
7 8
3
4 2
1 1
5 1
8
3 1
3 2
2 3
8 1
7 2
0 1
8 2
6 10

Wyjście:

-
1
2
-
3
2
3
3