Doomsday Protocol

Under the Doomsday Protocol, the surviving Kingsman agents must reach a certain wine shop. They may use the London Underground and the secret Kingsman tunnels. The Underground network is a tree, where vertices are stations and edges are the tracks between them. Stations are numbered from $1$ to $n$, and the wine shop is at station $1$. All tracks have the same length. Agents may be watched, and moving on the Underground can reveal their location, so they must travel on the Underground only away from the shop. In other words, they can ride from a station to an adjacent one only if the edge distance from the shop to the first station is less than the distance from the shop to the second. Each Kingsman tunnel connects two stations such that one can be reached from the other by moving on the Underground only away from the shop.

Merlin is working through scenarios for activating the Doomsday Protocol. Each scenario is defined by the station where the surviving agents start and the maximum number of Kingsman tunnels they may use. On the Underground they may travel any number of times, but only in the direction away from the shop. For each scenario, Merlin needs the station closest to the shop among those the agents can reach, since they must walk the rest of the way.

The first line contains one integer $n$, the number of stations ($2 \le n \le 200\,000$). Each of the next $n - 1$ lines contains two integers $a_i$ and $b_i$, the stations connected by an Underground track ($1 \le a_i, b_i \le n$).

The next line contains one integer $m$, the total number of Kingsman tunnels ($0 \le m \le 200\,000$). Each of the next $m$ lines contains two integers $u_i$ and $v_i$, the stations connected by a tunnel ($1 \le u_i, v_i \le n$, $u_i \neq v_i$). It is guaranteed that one can reach $u_i$ from $v_i$ by moving only away from the shop.

The next line contains one integer $q$, the number of scenarios ($0 \le q \le 200\,000$). Each of the next $q$ lines contains two integers $s_i$ and $k_i$, the station where the agents start and the number of Kingsman tunnels they may use ($1 \le s_i \le n$, $0 \le k_i \le m$).

For each scenario, print one integer on its own line: the number of the station closest to the shop among those the agents can reach.