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: # F - Tree and Constraints
  
  # Read input
  
  n = int(input())
  adj = {a: [] for a in range(1, n + 1)}
  for i in range(n - 1):
      a, b = map(int, input().split())
      adj[a].append((b, i))
      adj[b].append((a, i))
  m = int(input())
  ranges = [tuple(map(int, input().split())) for i in range(m)]
  
  # Subroutines
  
  
  def findpath(u, v, parent=None):
      """uからvへの経路 (辺の集合)"""
      if u == v:
          return set()
      for x, i in adj[u]:
          if x == parent:
              continue
          p = findpath(x, v, u)
          if p is not None:
              p.add(i)  # id of edge
              return p
      return None
  
  
  def powerset(seq, bag):
      """[(seqの部分集合s, bag[e] for e in s の和集合)]"""
      if len(seq) <= 1:
          yield ((seq[0],), bag[seq[0]])
          yield ((), set())
      else:
          for s, b in powerset(seq[1:], bag):
              yield ((seq[0],) + s, b | bag[seq[0]])
              yield (s, b)
  
  
  # Find paths
  
  paths = [findpath(u, v) for u, v in ranges]
  
  # いずれかの区間をすべて白にする塗り方の個数
  white = 0
  for s, b in powerset(list(range(m)), paths):
      l = len(s)
      if l <= 0:
          continue
      # b中の辺をすべて白にする塗り方の個数
      w = 2 ** (n - 1 - len(b))
      # 包除原理
      sign = -1 if l % 2 == 0 else 1
      white += sign * w
  
  # どの区間も黒を含む塗り方の個数
  coloring = 2 ** (n - 1) - white
  print(coloring)
  
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)"}]