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.readline
  n = int(input())
  Edge = [[] for i in range(n)]
  for i in range(n - 1):
      a, b = map(int, input().split())
      Edge[a - 1].append((b - 1, i))
      Edge[b - 1].append((a - 1, i))
  m = int(input())
  M = []
  for i in range(m):
      M.append(tuple(map(int, input().split())))
  
  inf = float("inf")
  path = [-1] * n  # 根から各点までのパスが通過する辺をbitで管理したもの
  path[0] = 0
  stack = [0]
  while stack:
      cur = stack.pop()
      for next, num in Edge[cur]:
          if path[next] == -1:
              path[next] = path[cur] | (1 << num)
              stack.append(next)
  
  
  def popcount(x):
      x = x - ((x >> 1) & 0x5555555555555555)
      x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
  
      x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F
      x = x + (x >> 8)
      x = x + (x >> 16)
      x = x + (x >> 32)
      return x & 0x0000007F
  
  
  passing = []  # Mの各u,vについて、通過する辺をbitで持ったもの
  for u, v in M:
      passing.append((path[u - 1] ^ path[v - 1]))
  
  ans = 2 ** (n - 1)
  # Mのすべての部分集合について符号付で足し合わせる
  for i in range(1, 2**m):
      i_ct = popcount(i)  # 満たすべき条件の数、これで符号を決める
      condition = 0
      for j in range(m):
          if i & (1 << j):  # j番目の条件を満たす
              condition = condition | passing[j]
      cond_ct = popcount(
          condition
      )  # iが表すMの部分集合の条件をすべて満たす場合にすべて白になる辺集合の要素数
  
      ans += pow((-1), i_ct) * pow(2, n - 1 - cond_ct)
  print(ans)
  
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)"}]