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
  
  readline = sys.stdin.readline
  MOD = 10**9 + 7
  INF = float("INF")
  sys.setrecursionlimit(10**5)
  
  
  def main():
      from collections import defaultdict, deque
      from itertools import combinations
  
      N = int(readline())
  
      edge = defaultdict(list)
  
      for i in range(N - 1):
          a, b = map(int, readline().split())
          edge[a - 1].append((b - 1, i))
          edge[b - 1].append((a - 1, i))
  
      def bfs(s, g):
          que = deque()
          que.append((s, []))
          visited = [False] * N
          visited[s] = True
  
          while que:
              cur, path = que.popleft()
              if cur == g:
                  return set(path)
              for nx, i in edge[cur]:
                  if not visited[nx]:
                      new_path = path + [i]
                      que.append((nx, new_path))
                      visited[nx] = True
  
      M = int(readline())
      constraints = []
      for _ in range(M):
          u, v = map(int, readline().split())
          u -= 1
          v -= 1
          constraints.append(bfs(u, v))
  
      cnt = 0
      for i in range(1, M + 1):
          sign = 1 if i % 2 == 1 else -1
          for per in combinations(range(M), r=i):
              incl = set()
              for x in per:
                  incl = incl.union(constraints[x])
              cnt += sign * 2 ** ((N - 1) - len(incl))
  
      print(2 ** (N - 1) - cnt)
  
  
  if __name__ == "__main__":
      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)"}]