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:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
ab = [LI() for _ in range(n-1)]
m = I()
uv = [LI() for _ in range(m)]

edge = [[] for i in range(n)]
lst = [[None]*n for i in range(n)]
cnt = 0
for i,[a,b] in enumerate(ab):
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
    lst[a-1][b-1] = i
    lst[b-1][a-1] = i

L = []
for u,v in uv:
    stack = deque()
    stack.append(u-1)
    flg = [True]*n
    par = [None]*n
    par[u-1] = -1
    while stack:
        x = stack.pop()
        if x == v-1:
            break
        flg[x] = False
        for y in edge[x]:
            if flg[y]:
                par[y] = x
                stack.append(y)
    tmp = v-1
    tmp2 = []
    while 1:
        if par[tmp] == -1:
            break
        tmp2.append(lst[tmp][par[tmp]])
        tmp = par[tmp]
    tmp2.sort()
    L.append(tmp2)

e = [0]*m
for i in range(m):
    x = 0
    for j in L[i]:
        x |= 1<<j
    e[i] = x

ans = 0
for i in range(1<<m):
    black = 0
    cnt = 0
    for j in range(m):
        if (i>>j & 1):
            cnt += 1
            black |= e[j]
    cnt2 = 0
    for j in range(n-1):
        if (black>>j & 1):
            cnt2 += 1
    if cnt % 2:
        ans -= 1<<(n-1-cnt2)
    else:
        ans += 1<<(n-1-cnt2)
print(ans)