output_description: Print the number of ways to paint the edges that satisfy all of the M
  conditions.
  
  * * *
input_description: 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
attempt: import sys
  
  input = sys.stdin.buffer.readline
  
  N = int(input())
  AB = [list(map(int, input().split())) for _ in range(N - 1)]
  M = int(input())
  UV = [list(map(int, input().split())) for _ in range(M)]
  
  
  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
  
  
  graph = [[] for _ in range(N + 1)]
  for a, b in AB:
      graph[a].append(b)
      graph[b].append(a)
  
  
  def make_tree(graph, root) -> (list, list):
      INF = 10**15
      dist = [INF] * len(graph)
      parent = [-1] * len(graph)
      stack = [root]
      dist[root] = 0
      parent[root] = root
      while stack:
          s = stack.pop()
          for g in graph[s]:
              if dist[g] > dist[s] + 1:
                  dist[g] = dist[s] + 1
                  parent[g] = s
                  stack.append(g)
      return dist, parent
  
  
  def lca(u, v, dist, parent):
      distu, distv = dist[u], dist[v]
      if distu > distv:
          for _ in range(distu - distv):
              u = parent[u]
      if distv > distu:
          for _ in range(distv - distu):
              v = parent[v]
      while u != v:
          u, v = parent[u], parent[v]
      return u
  
  
  dist, parent = make_tree(graph, 1)
  
  tree_lca = []
  for i in range(M):
      tmp = 0
      u, v = UV[i]
      l = lca(u, v, dist, parent)
      while u != l:
          tmp |= 1 << u
          u = parent[u]
      while v != l:
          tmp |= 1 << v
          v = parent[v]
      tree_lca.append(tmp)
  
  answer = 2 ** (N - 1)
  for i in range(1, 2**M):
      tmp = 0
      for j in range(M):
          if (i >> j) & 1:
              tmp |= tree_lca[j]
      cnt = popcnt(tmp)
  
      if popcnt(i) % 2 == 1:
          answer -= 2 ** (N - 1 - cnt)
      else:
          answer += 2 ** (N - 1 - cnt)
  
  print(answer)
  
problem_description: Statement
  
  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.
samples: [{"input": "3\n    1 2\n    2 3\n    1\n    1 3", "output": "3\n    \n\nThe tree in this input is shown below:  \n  \n![Figure](https://img.atcoder.jp/ghi/5b0208ab1e3bb39a5d4fb7bafbfc448e.png)  \n  \nAll of the M restrictions will be satisfied if Edge 1 and 2 are respectively\npainted (white, black), (black, white), or (black, black), so the answer is 3.\n\n* * *"}, {"input": "2\n    1 2\n    1\n    1 2", "output": "1\n    \n\nThe tree in this input is shown below:  \n  \n![Figure](https://img.atcoder.jp/ghi/d08b3f53dfa4857fe9ffe13fa5d7ae69.png)  \n  \nAll of the M restrictions will be satisfied only if Edge 1 is painted black,\nso the answer is 1.\n\n* * *"}, {"input": "5\n    1 2\n    3 2\n    3 4\n    5 3\n    3\n    1 3\n    2 4\n    2 5", "output": "9\n    \n\nThe tree in this input is shown below:  \n  \n![Figure](https://img.atcoder.jp/ghi/386502bb3c85e0bb5aee64e4e7c087a1.png)  \n  \n\n* * *"}, {"input": "8\n    1 2\n    2 3\n    4 3\n    2 5\n    6 3\n    6 7\n    8 6\n    5\n    2 7\n    3 5\n    1 6\n    2 8\n    7 8", "output": "62\n    \n\nThe tree in this input is shown below:  \n  \n![Figure](https://img.atcoder.jp/ghi/955fa8fd8af658abb24ff2f68b9997be.png)"}]