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:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


# https://atcoder.jp/contests/abc152/submissions/9619555

import sys
readline = sys.stdin.readline



n = I()
G = [[] for _ in range(n)]
for i in range(n - 1):
    u, v = LI()
    G[u - 1] += [(i, v - 1)]
    G[v - 1] += [(i, u - 1)]


def dfs(root):
    q = [root]
    path_bit = [-1] * n
    path_bit[root] = 0
    while q:
        u = q.pop()
        for i, v in G[u]:
            if path_bit[v] != -1:
                continue
            path_bit[v] = path_bit[u] | 1 << i
            q += [v]
    return path_bit



def popcnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
    return c


m = I()
cond = LIR(m)
path_bit = dfs(0)
cond_bit = [0] * m
for j, (u, v) in enumerate(cond):
    cond_bit[j] = path_bit[u - 1] ^ path_bit[v - 1]

L = [0] * (2 ** m)
C = [0] * n
for i in range(2 ** m):
    if i != 0:
        L[i] = L[(i ^ (i & -i))] | cond_bit[(i & -i).bit_length() - 1]
# それぞれの条件を満たさないものを全事象から引く。
# 次に、2個同時に条件を満たさないものをたす。という要領。
    cond_cnt = popcnt(i)
# p_cnt が満たさない条件の数。
    if cond_cnt % 2:
        C[n - 1 - popcnt(L[i])] -= 1
    else:
        C[n - 1 - popcnt(L[i])] += 1


ans = 0
for i in range(n):
    ans += 2 ** i * C[i]


print(ans)