Minimum Distinct Islands Visiting

JOI Kingdom is an insular country consisting of \(N\) islands connected by \(N-1\) bidirectional bridges forming a tree. There are \(M\) sightseeing spots, each located on some island. Additionally, there are \(Q\) travelers. The \(k\)-th traveler wants to visit all sightseeing spots numbered from \(L_k\) to \(R_k\). Since each sightseeing spot is located in a predetermined island, the traveler must visit all islands corresponding to the spots \(C_{L_k}, C_{L_k+1}, \dots, C_{R_k}\>.

The traveler is allowed to:

• Choose any island as a starting point (by airplane).
• Visit any sightseeing spot in the current island.
• Travel from one island to another via a bridge (the islands form a connected tree).
• Leave JOI Kingdom by airplane.

The goal is to minimize the number of distinct islands visited while still visiting all required sightseeing spots. Note that the minimum number of distinct islands that must be visited is equivalent to the number of vertices in the minimal subtree connecting all the islands containing the required sightseeing spots. Formally, if \(S\) is the set of islands corresponding to sightseeing spots \(C_{L_k}, \dots, C_{R_k}\), the answer is the number of vertices in the Steiner tree of \(S\) in the given tree.

You are given the description of the islands and bridges, the locations of the sightseeing spots, and the \(Q\) queries. For each query, compute the minimum number of distinct islands that must be visited.

inputFormat

The input is given in the following format:

N
A₁ B₁
A₂ B₂
... 
Aₙ₋₁ Bₙ₋₁
M
C₁
C₂
... 
Cₘ
Q
L₁ R₁
L₂ R₂
... 
L_Q R_Q

Here, the first integer \(N\) denotes the number of islands. Each of the next \(N-1\) lines contains two integers \(A_i\) and \(B_i\), representing a bidirectional bridge between islands \(A_i\) and \(B_i\). It is guaranteed that the islands form a tree (i.e. they are connected and there is exactly one simple path between any two islands).

Next, \(M\) denotes the number of sightseeing spots. The following \(M\) lines each contain a single integer \(C_j\) which represents the island on which the \(j\)-th sightseeing spot is located.

Finally, \(Q\) denotes the number of travelers (queries). Each of the next \(Q\) lines contains two integers \(L_k\) and \(R_k\). For the \(k\)-th traveler, the set of required sightseeing spots is \(\{C_{L_k}, C_{L_k+1}, \dots, C_{R_k}\}\>.

outputFormat

For each query, output the minimum possible number of distinct islands that must be visited, each on a separate line.

sample

5
1 2
2 3
2 4
1 5
3
2
3
4
3
1 1
1 3
2 3

1
3
3