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:
# = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
# = list(input())
# = [tuple(map(int, input().split())) for _ in range(n)]

n = int(input())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]
m = int(input())
uv = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(m)]

e = [[] for _ in range(n)]
i = 0
for a, b in ab:
    e[a].append([b, i])
    e[b].append([a, i])
    i += 1

def func(x, g, p):
    #print(x, g, p, e[x])
    if len(e[x]) == 1 and p != -1:
        return -1
    for edge in e[x]:
        if edge[0] == p:
            continue
        elif edge[0] == g:
            #print(edge)
            return 1 << edge[1]
        temp = func(edge[0], g, x)
        #print(temp, x, g, p)
        if temp >= 0:
            #print(edge[1])
            return temp + (1 << edge[1])
    return -1

p = []
for u, v in uv:
    p.append(func(u, v, -1))

#print(p)
flag = -1
ans = 2 ** (n-1)
#print(ans)
base = 2 ** (n-1)
for i in range(1, 1 << m):
    temp = list(reversed(list(str(bin(i)))[2:]))
    c = 0
    #print(temp)
    for j, x in enumerate(temp):
        if x == '1':
            c = c | p[j]
    #print(bin(base + c))
    hoge = str(bin(base + c)).count('0') - 1
    if temp.count('1') % 2 == 0:
        flag = 1
    else:
       flag = -1
    ans += flag * (2 ** hoge)
    #flag *= -1
print(ans)