Highways

Byteland is a small country with $n$ cities connected by $n-1$ bidirectional roads. Using only roads, there is exactly one way to travel between any two cities, so the road network forms a tree. Because that single path causes heavy traffic, several highways were built, and each highway directly connects some pair of cities.

A route is a sequence of roads and highways along which every visited city is distinct (a simple path). For every pair of cities $x$ and $y$ there is exactly one route that uses no highway at all; we call it the main route between $x$ and $y$ (the unique path through the road network).

To travel from city $x$ to city $y$, people may take the main route, or take an alternative route that uses exactly one highway. An alternative route is allowed only if it shares no city with the main route other than the endpoints $x$ and $y$.

For each queried pair of cities, report the number of routes people can take between them (the main route together with every allowed alternative route).

The first line contains a single integer $n$ ($1 \le n \le 10^5$), the number of cities. Cities are numbered from $1$ to $n$.

Each of the next $n-1$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$), meaning cities $a_i$ and $b_i$ are connected by a road.

The next line contains an integer $m$ ($1 \le m \le 10^5$), the number of highways. Each of the next $m$ lines gives the two cities that one highway connects.

The next line contains an integer $q$ ($1 \le q \le 5 \cdot 10^5$), the number of queries. Each of the next $q$ lines contains two integers $x$ and $y$, a query about travel between cities $x$ and $y$. Highways and queries are given in the same two-integer format as the roads.

Print exactly $q$ lines. The $i$-th line must contain a single integer, the number of routes for the $i$-th query.