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
from heapq import heappop, heappush


class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, From, To, cost=1):
        self.graph[From].append((To,cost))

    def get_nodes(self):
        return self.graph.keys()
class Dijkstra(object):

    def __init__(self, graph, start):
        self.g = graph.graph
        self.dist = defaultdict(lambda:float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)
        self.Q = []
        heappush(self.Q,(self.dist[start], start))

        while  self.Q:
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, cost in self.g[u]:
                alt = dist_u + cost
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q,(alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]


N = int(input())
g = Graph()
d = {}
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    d[(min(a,b),max(a,b))] = i
    g.add_edge(a,b)
    g.add_edge(b,a)

M = int(input())
l = [0]*M
for i in range(M):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    dij = Dijkstra(g,u)
    path = dij.shortest_path(v)
    for j in range(len(path)-1):
        a,b = path[j],path[j+1]
        l[i] += 2**d[(min(a,b),max(a,b))]

c = [0]*(M+1)
p2 = [2**i for i in range(50)]
for n in range(2**M):
    cnt = 0
    x = 0
    for i in range(M):
        if n&p2[i]==p2[i]:
            cnt += 1
            x |= l[i]
    y = 0
    for i in range(N-1):
        if x&p2[i]==p2[i]:
            y += 1
    c[cnt] += p2[N-1-y]

ans = 0
for i in range(M+1):
    if i%2==0:
        ans += c[i]
    else:
        ans -= c[i]

print(ans)