Problem: We have a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and Vertex b_i.
Consider painting each of these edges white or black. There are 2^{N-1} such ways to paint the edges. Among them, how many satisfy all of the following M restrictions?

* The i-th (1 \leq i \leq M) restriction is represented by two integers u_i and v_i, which mean that the path connecting Vertex u_i and Vertex v_i must contain at least one edge painted black.

Constraints

* 2 \leq N \leq 50
* 1 \leq a_i,b_i \leq N
* The graph given in input is a tree.
* 1 \leq M \leq \min(20,\frac{N(N-1)}{2})
* 1 \leq u_i < v_i \leq N
* If i \not= j, either u_i \not=u_j or v_i\not=v_j
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1
:
a_{N-1} b_{N-1}
M
u_1 v_1
:
u_M v_M


Output

Print the number of ways to paint the edges that satisfy all of the M conditions.

Examples

Input

3
1 2
2 3
1
1 3


Output

3


Input

2
1 2
1
1 2


Output

1


Input

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


Output

9


Input

8
1 2
2 3
4 3
2 5
6 3
6 7
8 6
5
2 7
3 5
1 6
2 8
7 8


Output

62

Solution (in PYTHON3):

Solution:

"""
20個しかないので包除原理？
使う、使わないで 2**20通り

答え = 2**N - 1満たさない + 2つ満たさない - 3つ満たさない…
で表される

各場合はいずれかのパスに属す点以外は自由に塗れる
各パス上の点をbitで管理
黒に塗ってはいけない点のかずをあぶりだす

計算量は 2**20

"""
from collections import deque

N = int(input())

dic = {}

for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1
    c = N+i

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []
    dic[c] = []

    dic[a].append(c)
    dic[b].append(c)
    dic[c].append(a)
    dic[c].append(b)

M = int(input())
bitlis = []

for loop in range(M):

    u,v = map(int,input().split())
    u -= 1
    v -= 1
    
    bits = [0] * N + [2**i for i in range(N-1)]
    dis = [float("inf")] * (2*N-1)
    dis[u] = 0

    q = deque([u])

    while len(q) > 0:

        now = q.popleft()

        for nex in dic[now]:
            if dis[nex] > dis[now] + 1:
                dis[nex] = dis[now] + 1
                bits[nex] += bits[now]
                q.append(nex)

    bitlis.append(bits[v])

#print (bitlis)
uselis = [0] * (M+1)

for use in range(2**M):

    white = 0
    usenum = 0
    for i in range(M):
        if use & (2**i) > 0:
            white |= bitlis[i]
            usenum += 1

    able = N-1
    ws = format(white,"b")
    for i in ws:
        if i == "1":
            able -= 1

    uselis[usenum] += 2 ** able

#print (uselis)
ans = 2 ** (N-1)

for i in range(M):

    i += 1

    if i % 2 == 1:
        ans -= uselis[i]
    else:
        ans += uselis[i]

print (ans)