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 itertools import combinations


# nは頂点数。lは[頂点,頂点]がn-1個入ったリスト。Tree(n, l)としてobjectを生成。
class Tree():
    def __init__(self, n, l):

        self.n = n

        # 隣接する頂点のリストが格納された辞書
        self.w = {}
        for i in range(n - 1):
            a, b, path = l[i]
            if a in self.w:
                self.w[a].append((b, path))
            else:
                self.w[a] = [(b, path)]
            if b in self.w:
                self.w[b].append((a, path))
            else:
                self.w[b] = [(a, path)]


    # rootを根とした時の、各頂点の一つ上の親の頂点が格納された辞書を返す。
    def make_parents_list(self, root):
        self.parents = {}
        que = []
        seen = {}
        for i in range(1, n + 1):
            seen[i] = 0
        self.parents[root] = (None, None)
        seen[root] = 1
        que.append(root)
        while len(que) != 0:
            node = que.pop()
            for k in range(len(self.w[node])):
                node_2, path_2 = self.w[node][k]
                if seen[node_2] == 0:
                    seen[node_2] = 1
                    que.append(node_2)
                    self.parents[node_2] = (node, path_2)
                else:
                    continue
        return self.parents


    # 頂点uと頂点vの最小共通祖先(LCA)を求める。
    def lca(self, root, u, v):
        ancestors = set()
        if self.parents is None:
            parents = self.make_parents_list(root)
        else:
            parents = self.parents
        parent = u

        while parent is not None:
            ancestors.add(parent)
            parent = parents[parent][0]

        node = v
        while node not in ancestors:
            node = parents[node][0]

        return node


n = int(input())
l = []
for i in range(n - 1):
    a, b = [int(_) for _ in input().split()]
    l.append((a, b, i))
tree = Tree(n, l)
seiyaku = []
parents = tree.make_parents_list(1)
m = int(input())
for i in range(m):
    u, v = [int(_) for _ in input().split()]
    parent_node = tree.lca(1, u, v)
    s = set()
    node = u
    while node != parent_node:
        s.add(parents[node][1])
        node = parents[node][0]
    node = v
    while node != parent_node:
        s.add(parents[node][1])
        node = parents[node][0]
    seiyaku.append(s)

ans = 2 ** (n - 1)
for i in range(1, 2 ** m):
    i_bin = format(i, '0' + str(m) + 'b')
    k = 0
    q = []
    for j in range(m):
        if i_bin[j] == '1':
            q.append(j)
            k += 1
        else:
            continue
    s = set()
    for x in q:
        s |= seiyaku[x]
    ans += (-1) ** k * 2 ** (n - 1 -len(s))
    # print('*****************')
    # print('i_bin = ' ,i_bin)
    # print('k = ', k)
    # print('q = ', q)
    # print('s = ', s)
    # print('len(s) = ', len(s))
    # print('(-1) ** k * 2 ** (n - 1 - len(s)) = ', (-1) ** k * 2 ** (n - 1 - len(s)))
    # print('ans = ', ans)
print(ans)

# print('+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++')

# cnt = 2**(n-1)

# f = 0
# for i in range(1, m+1):
#     flag = 1
#     if i % 2 == 1:
#         flag = -1
#     cc = combinations(list(range(m)), i)
#     for c in cc:
#         s = set()
#         for j in c:
#             s |= seiyaku[j]
#         cnt += (2**(n-1-len(s)))*flag
#         f += 1
#         print('*****************')
#         print('c = ' ,c)
#         print('flag = ', flag)
#         print('s = ', s)
#         print('len(s) = ', len(s))
#         print('(2**(n-1-len(s)))*flag = ', (2**(n-1-len(s)))*flag)
#         print('cnt = ', cnt)
# print(cnt)
# print('f = ', f)