E. Древляндия и вирусы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Древляндии $$$n$$$ городов, соединенных $$$n - 1$$$ двунаправленными дорогами таким образом, что из любого города можно добраться в любой другой (другими словами, граф городов и дорог является деревом). Древлядния готовится к сезонной вирусной эпидемии, и сейчас они пытаются оценить различные сценарии распространения инфекции.

В каждом из сценариев некоторые города исходно заражены различными видами вирусов. Пусть в $$$i$$$-м сценарии присутствует $$$k_i$$$ типов вирусов. Обозначим за $$$v_j$$$ исходный город для вируса $$$j$$$, и за $$$s_j$$$ скорость распространения вируса $$$j$$$. Распространение вирусов происходит пошагово: сперва распространяется вирус $$$1$$$, затем вирус $$$2$$$, и так далее. После распространения вируса $$$k_i$$$ процесс начинается заново с вируса $$$1$$$.

Шаг распространения вируса $$$j$$$ происходит следующим образом. Для каждого города $$$x$$$, еще не зараженного никаким вирусом в начале шага, заражение вирусом $$$j$$$ происходит тогда и только тогда, когда найдется другой город $$$y$$$ со следующими свойствами:

  • город $$$y$$$ заражен вирусом $$$j$$$ в начале шага;
  • путь между городами $$$x$$$ и $$$y$$$ содержит не более $$$s_j$$$ рёбер;
  • ни один город на пути между $$$x$$$ и $$$y$$$ (не считая $$$y$$$) не был заражен никаким вирусом в начале шага.

Если город заражен вирусом, он всегда остается зараженным и больше не может быть заражен никаким другим вирусом. Распространение вирусов останавливается, когда все города заражены.

Вам требуется обработать $$$q$$$ независимых сценариев. Каждый сценарий описывается $$$k_i$$$ типами вирусов и списком из $$$m_i$$$ важных городов. Для каждого важного города определите тип вируса, которым он будет заражен в конце сценария.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — количество городов в Древляндии.

Следующие $$$n - 1$$$ строк описывают дороги. $$$i$$$-я из этих строк содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$) — номера городов, соединенных $$$i$$$-й дорогой. Гарантируется, что данный граф городов и дорог является деревом.

Следующая строка содержит одно целое число $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — количество сценариев заражения. Далее следуют $$$q$$$ описаний сценариев.

Описание $$$i$$$-го сценария начинается со строки, содержащей два целых числа $$$k_i$$$ и $$$m_i$$$ ($$$1 \leq k_i, m_i \leq n$$$) — количество типов вируса и количество важных городов в этом сценарии соответственно. Гарантируется, что $$$\sum_{i = 1}^ q k_i$$$ и $$$\sum_{i = 1}^ q m_i$$$ не превосходят $$$2 \cdot 10^5$$$.

Следующие $$$k_i$$$ строк описывают типы вирусов. $$$j$$$-я из этих строк содержит два целых числа $$$v_j$$$ и $$$s_j$$$ ($$$1 \leq v_j \leq n$$$, $$$1 \leq s_j \leq 10^6$$$) – номер исходного города и скорость распространения вируса $$$j$$$. Гарантируется, что исходные города всех типов вирусов внутри одного сценария различны.

Следующая строка содержит $$$m_i$$$ различных чисел $$$u_1, \ldots, u_{m_i}$$$ ($$$1 \leq u_j \leq n$$$) — номера важных городов .

Выходные данные

Выведите $$$q$$$ строк. $$$i$$$-я строка должна содержать $$$m_i$$$ целых чисел — номера типов вирусов, которыми будут заражены города $$$u_1, \ldots, u_{m_i}$$$ соответственно в конце $$$i$$$-го сценария.

Пример
Входные данные
7
1 2
1 3
2 4
2 5
3 6
3 7
3
2 2
4 1
7 1
1 3
2 2
4 3
7 1
1 3
3 3
1 1
4 100
7 100
1 2 3
Выходные данные
1 2
1 1
1 1 1