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()))

def dfs(s,g,p):
    global tmp
    if s == g:
        tmp = []
        return True
    for (v,i) in edge[s]:
        if v == p:
            continue
        if dfs(v,g,s):
            tmp.append(i)
            return True
    return False

n = I()
edge = [[] for i in range(n)]
for i in range(n-1):
    a,b = LI()
    a -= 1
    b -= 1
    edge[a].append((b,i))
    edge[b].append((a,i))

m = I()
lst = []
tmp = []
for _ in range(m):
    u,v = LI()
    u -= 1
    v -= 1
    dfs(u,v,-1)
    lst.append(tmp)

"""m個の制約がどの辺を通るかbitで管理"""
e = [0]*m
for i in range(m):
    x = 0
    for j in lst[i]:
        x |= 1<<j
    e[i] = x

"""包除原理"""
ans = 0
for i in range(1<<m):
    black = 0 #制約の通る辺をbitで管理
    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) #-2**((n-1本の辺)-(制約内の辺の本数))
    else:
        ans += 1<<(n-1-cnt2) #+2**((n-1本の辺)-(制約内の辺の本数))
print(ans)