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.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int adj[][] = new int[N][N];
		for(int i = 0 ; i < N - 1 ; ++i){
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			adj[a][b] = i + 1;
			adj[b][a] = i + 1;
		}
		int M = sc.nextInt();
		List<List<Integer>> rules = new ArrayList<List<Integer>>();
		for(int i = 0 ; i < M ; ++i){
			int u = sc.nextInt() - 1;
			int v = sc.nextInt() - 1;
			Queue<Integer> q = new LinkedList<Integer>();
			int back[] = new int[N];
			Arrays.fill(back, -1);
			back[u] = u;
			q.add(u);
			List<Integer> path = new ArrayList<Integer>();
			while(!q.isEmpty()){
				int cur = q.poll();
				if(cur == v){
					while(back[cur] != u){
						int b = back[cur];
						path.add(adj[cur][b] - 1);
						cur = b;
					}
					path.add(adj[cur][u] - 1);
					break;
				}
				for(int a = 0 ; a < N ; ++a){
					if(adj[cur][a] == 0){
						continue;
					}
					if(back[a] != -1){
						continue;
					}
					back[a] = cur;
					q.add(a);
				}
			}
			rules.add(path);			
		}
		long ret = 0;
		int B = 1 << M;
		for(int i = 1 ; i < B ; ++i){
			int nb = Integer.bitCount(i);
			long ns = 0;
			for(int j = 0 ; j < M ; ++j){
				if((i & (1 << j)) == 0){
					continue;
				}
				List<Integer> l = rules.get(j);
				for(int r : l){
					ns = ns | (1L << r);
				}
			}
			int nb2 = Long.bitCount(ns);
			long pat = 1L << (N - 1 - nb2);
			if(nb % 2 == 0){
				ret = ret - pat;
			}else{
				ret = ret + pat;
			}
		}
		ret = (1L << (N - 1)) - ret;
		System.out.println(ret);
	}
}