There are $$$n$$$ cities in Treeland connected with $$$n - 1$$$ bidirectional roads in such that a way that any city is reachable from any other; in other words, the graph of cities and roads is a tree. Treeland is preparing for a seasonal virus epidemic, and currently, they are trying to evaluate different infection scenarios.
In each scenario, several cities are initially infected with different virus species. Suppose that there are $$$k_i$$$ virus species in the $$$i$$$-th scenario. Let us denote $$$v_j$$$ the initial city for the virus $$$j$$$, and $$$s_j$$$ the propagation speed of the virus $$$j$$$. The spread of the viruses happens in turns: first virus $$$1$$$ spreads, followed by virus $$$2$$$, and so on. After virus $$$k_i$$$ spreads, the process starts again from virus $$$1$$$.
A spread turn of virus $$$j$$$ proceeds as follows. For each city $$$x$$$ not infected with any virus at the start of the turn, at the end of the turn it becomes infected with virus $$$j$$$ if and only if there is such a city $$$y$$$ that:
Once a city is infected with a virus, it stays infected indefinitely and can not be infected with any other virus. The spread stops once all cities are infected.
You need to process $$$q$$$ independent scenarios. Each scenario is described by $$$k_i$$$ virus species and $$$m_i$$$ important cities. For each important city determine which the virus it will be infected by in the end.
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of cities in Treeland.
The following $$$n - 1$$$ lines describe the roads. The $$$i$$$-th of these lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$) — indices of cities connecting by the $$$i$$$-th road. It is guaranteed that the given graph of cities and roads is a tree.
The next line contains a single integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — the number of infection scenarios. $$$q$$$ scenario descriptions follow.
The description of the $$$i$$$-th scenario starts with a line containing two integers $$$k_i$$$ and $$$m_i$$$ ($$$1 \leq k_i, m_i \leq n$$$) — the number of virus species and the number of important cities in this scenario respectively. It is guaranteed that $$$\sum_{i = 1}^ q k_i$$$ and $$$\sum_{i = 1}^ q m_i$$$ do not exceed $$$2 \cdot 10^5$$$.
The following $$$k_i$$$ lines describe the virus species. The $$$j$$$-th of these lines contains two integers $$$v_j$$$ and $$$s_j$$$ ($$$1 \leq v_j \leq n$$$, $$$1 \leq s_j \leq 10^6$$$) – the initial city and the propagation speed of the virus species $$$j$$$. It is guaranteed that the initial cities of all virus species within a scenario are distinct.
The following line contains $$$m_i$$$ distinct integers $$$u_1, \ldots, u_{m_i}$$$ ($$$1 \leq u_j \leq n$$$) — indices of important cities.
Print $$$q$$$ lines. The $$$i$$$-th line should contain $$$m_i$$$ integers — indices of virus species that cities $$$u_1, \ldots, u_{m_i}$$$ are infected with at the end of the $$$i$$$-th scenario.
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
Name |
---|