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.util.*;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static Scanner sc = new Scanner(System.in);
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    long mod = 1000000000+7;
    List<Integer>[] tree;
    int n;
    public static void main(String[] args) throws IOException {
        Main main = new Main();
//        main.solve();
        out.println(main.solve());
        out.flush();
    }
    long solve() throws IOException {
        n = sc.nextInt();
        tree = new List[n];
        for(int i=0;i<n;i++) tree[i] = new ArrayList<>(25);
        for(int i=0;i<n-1;i++){
            int a = sc.nextInt()-1, b = sc.nextInt()-1;
            tree[a].add(b); tree[b].add(a);
        }
        int m = sc.nextInt();
        int[][] restri = new int[m][];
        for(int i=0;i<m;i++){
            int u = sc.nextInt()-1, v = sc.nextInt()-1;
            restri[i] = new int[]{u,v};
        }
        Set<Integer>[] white = new Set[m];
        for(int i=0;i<m;i++){
            int u = restri[i][0], v = restri[i][1];
            white[i] = getEdges(u,v);
        }
        long sub = 0; // how many illegal choices are there
        for(int state=1; state<(1<<m); state++){
            // then the relevant paths are all white
            int cnt = 0;
            Set<Integer> tot_white = new HashSet<>(50);
            for(int j=0; j<m; j++){
                int mask = 1<<j;
                if((mask&state)>0){
                    // we let this restriction unfulfilled
                    tot_white.addAll(white[j]);
                    cnt++;
                }
            }
            int remain = n-1-tot_white.size();
            if(cnt%2==1) sub += 1L<<remain;
            else sub -= 1L<<remain;
        }
        long ans = (1L<<(n-1))-sub;
        return ans;
    }
    Set<Integer> getEdges(int u, int v){
        int[] prev = new int[n];
        dfs(u,u,prev,v);
        Set<Integer> ans = new HashSet<>();
        // since prev[u] = u;
        while(prev[v]!=v){
            ans.add(getKey(v, prev[v]));
            v = prev[v];
        }
        return ans;
    }
    void dfs(int cur, int from, int[] prev, int target){
        prev[cur] = from;
        if(cur==target) return;
        for(int to:tree[cur]){
            if(to==from) continue;
            dfs(to, cur, prev, target);
        }
    }
    int getKey(int a, int b){
        return Math.min(a,b)*n+Math.max(a,b);
    }

}