Treeland and Viruses

有一棵有 $n$ 个节点的树，$q$ 次询问（询问互相独立），每次给定 $k_i$ 个颜色，每个颜色有一个起始点 $v_j$ 和移动速度 $s_j$，每一个颜色在每一次操作中会使它周围没有被染色的连通块上与它的距离不超过 $s_j$ 的点全部染为这一个颜色，每一轮中，颜色从 $1$ 到 $k_i$ 依次开始操作，一直到所有点全部被染色为止，再询问 $m_i$ 个关键点的颜色。

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: - city $ y $ was infected with virus $ j $ at the start of the turn; - the path between cities $ x $ and $ y $ contains at most $ s_j $ edges; - all cities on the path between cities $ x $ and $ y $ (excluding $ y $ ) were uninfected with any virus at the start of the turn. 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