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:
import sys
readline = sys.stdin.readline
popcntsum = ((1<<64) - 1)
Fa = [0] + [popcntsum//((1<<(1<<(i-1)))+1) for i in range(1,7)]
Fb = [0] + [Fa[i]<<(1<<(i-1)) for i in range(1,7)]
fila1 = Fa[1]
filb1 = Fb[1]
fila2 = Fa[2]
filb2 = Fb[2]
fila3 = Fa[3]
filb3 = Fb[3]
fila4 = Fa[4]
filb4 = Fb[4]
fila5 = Fa[5]
filb5 = Fb[5]
fila6 = Fa[6]
filb6 = Fb[6]
def popcount(x):
    x = (x&fila1) + ((x&filb1)>>1)
    x = (x&fila2) + ((x&filb2)>>2)
    x = (x&fila3) + ((x&filb3)>>4)
    x = (x&fila4) + ((x&filb4)>>8)
    x = (x&fila5) + ((x&filb5)>>16)
    x = (x&fila6) + ((x&filb6)>>32)
    return x

def parorder(Edge, p):
    N = len(Edge)
    par = [0]*N
    par[p] = -1
    stack = [p]
    order = []
    Enum = [None]*N
    visited = set([p])
    ast = stack.append
    apo = order.append
    while stack:
        vn = stack.pop()
        apo(vn)
        for vf, num in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            Enum[vf] = num
            ast(vf)
    return par, order, Enum

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i, v in enumerate(p[1:], 1):
        res[v].append(i)
    return res


N = int(readline())
Edge = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append((b, i))
    Edge[b].append((a, i))

root = 0
P, L, Enum = parorder(Edge, root)
#C = getcld(P)

M = int(readline())
Q = [tuple(map(int, readline().split())) for _ in range(M)]

dp = [0]*(1<<M)
ans = pow(2, N-1)
for S in range(1, 1<<M):
    pc = popcount(S)
    if pc == 1:
        i = (-S&S).bit_length() - 1
        table = [False]*(N-1)
        u, v = Q[i]
        u -= 1
        v -= 1
        while u != root:
            table[Enum[u]] = not table[Enum[u]]
            u = P[u]
        while v != root:
            table[Enum[v]] = not table[Enum[v]]
            v = P[v]
        res = 0
        for t in table:
            res <<= 1
            res |= t
        dp[S] = res
    else:
        dp[S] = dp[S^(-S&S)]|dp[-S&S]
    
    ans += (-1)**(pc%2)*pow(2, N-1-popcount(dp[S]))
print(ans)