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: def main():
      from itertools import combinations
  
      n = int(input())
      ab = [tuple(sorted(list(map(int, input().split())))) for _ in [0] * (n - 1)]
      m = int(input())
      uv = [list(map(int, input().split())) for _ in [0] * m]
      g = [[] for _ in [0] * n]
      [g[a - 1].append(b - 1) for a, b in ab]
      [g[b - 1].append(a - 1) for a, b in ab]
  
      d = dict()
      for i, (a, b) in enumerate(ab):
          d[(a - 1, b - 1)] = i
  
      def tree_path(root, goal):
          d = [-1] * n  # 根からの距離
          d[root] = 0
          q = [root]
          cnt = 0
          while q:  # BFS
              cnt += 1
              qq = []
              while q:
                  i = q.pop()
                  for j in g[i]:
                      if d[j] == -1:
                          d[j] = cnt
                          qq.append(j)
              q = qq
          now = goal
          path = [goal]
          while True:
              dist = d[now]
              for i in g[now]:
                  if d[i] < dist:
                      now = i
                      path.append(i)
                      break
              if dist == 1:
                  break
          return path
  
      seiyaku = [set() for _ in [0] * m]
  
      for i, (u, v) in enumerate(uv):
          path = tree_path(u - 1, v - 1)
          for j in range(len(path) - 1):
              x, y = min(path[j], path[j + 1]), max(path[j], path[j + 1])
              seiyaku[i].add(d[(x, y)])
  
      cnt = 2 ** (n - 1)
  
      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
      print(cnt)
  
  
  main()
  
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)"}]