Problem: 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.

Constraints

* 2 \leq N \leq 50
* 1 \leq a_i,b_i \leq N
* The graph given in input is a tree.
* 1 \leq M \leq \min(20,\frac{N(N-1)}{2})
* 1 \leq u_i < v_i \leq N
* If i \not= j, either u_i \not=u_j or v_i\not=v_j
* All values in input are integers.

Input

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


Output

Print the number of ways to paint the edges that satisfy all of the M conditions.

Examples

Input

3
1 2
2 3
1
1 3


Output

3


Input

2
1 2
1
1 2


Output

1


Input

5
1 2
3 2
3 4
5 3
3
1 3
2 4
2 5


Output

9


Input

8
1 2
2 3
4 3
2 5
6 3
6 7
8 6
5
2 7
3 5
1 6
2 8
7 8


Output

62

Solution (in JAVA):

Solution:


import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.Stack;




public class Main{
	public static class FastReader {
		BufferedReader br;
		StringTokenizer root;
		
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (root == null || !root.hasMoreTokens()) {
				try {
					root = new StringTokenizer(br.readLine());
				} catch (Exception r) {
					r.printStackTrace();
				}
			}
			return root.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
	
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	static int mod = (int) (1e9+7),n;
	static long cf = 998244353;
    static final int MAX = (int) 1e16;
    public static List<Edge>[] edges;
    public static int[][] parent;
    public static int col = 20;
    public static long[] Bit;
    public static long[] fact,inv;
    public  static int[] prime; 
    public static long[] seg,lazy;
	public static FastReader sc = new FastReader();
	public static void main(String[] args) {
	//	Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		edges = new ArrayList[n];
		for(int i=0;i<n;++i) edges[i] = new ArrayList<>();
		for(int i=1;i<n;++i) {
			int u = sc.nextInt()-1;
			int v = sc.nextInt()-1;
			edges[u].add(new Edge(v,i));
			edges[v].add(new Edge(u,i));
		}
		int m = sc.nextInt();
		long[] white = new long[m];
		long ans = 0;
		for(int i=0;i<m;++i) {
			int u = sc.nextInt()-1;
			int v = sc.nextInt()-1;
			cnt = 0;
			dfs(u,v,-1);
			white[i] = cnt;
		}
		for(int i=0;i<1L<<m;++i) {
			long temp = 0;
			for(int j=0;j<m;++j) {
				if((i&(1L<<j))!=0)
					temp|=white[j];
			}
			long C = Long.bitCount(temp);
			if((Integer.bitCount(i)&1) == 0) ans+=1L<<(n-1-C);
			else ans-=1L<<(n-1-C);
		
		
	}
		out.println(ans);
		out.close();
	}
	static long cnt;
	private static boolean dfs(int u, int v, int p) {
		if(u == v) return true;
		for(Edge e : edges[u]) {
			if(e.to != p) {
				if(dfs(e.to,v,u)) {
					cnt|=1L<<e.id;
					return true;
				}
			}
		}
		return false;
	}
	static class Edge{
		int to;
		int id;
		Edge(int to,int id){
			this.to = to;
			this.id = id;
		}
	}
}