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.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;

public class Main {

    static Scanner sc = null;
    static PrintWriter pw = null;

    //
//
//


    static {

        sc = new Scanner(System.in);
    }
//    static {
//        sc = new Scanner("5 5 \n" +
//                "20 23 12 18 2 \n" +
//                "19 14 17 6 9 \n" +
//                "24 15 13 16 10 \n" +
//                "4 1 8 3 5 \n" +
//                "11 7 21 22 25 ");
//
//    }
//    static Scanner sc = new Scanner("5\n" +
//            "5 3\n" +
//            "4 1\n" +
//            "9 1\n" +
//            "2 1\n" +
//            "5 4\n" +
//            "1 1\n" +
//            "8 2\n" +
//            "3 2\n" +
//            "6 1\n" +
//            "12 6\n" +
//            "15 2\n" +
//            "22 1\n" +
//            "4 2\n" +
//            "14 1\n" +
//            "23 1\n" +
//            "19 2\n" +
//            "53 9\n" +
//            "7 1\n" +
//            "19 1\n" +
//            "23 2\n" +
//            "40 2\n" +
//            "54 2\n" +
//            "81 1\n" +
//            "85 2\n" +
//            "94 1\n" +
//            "102 1\n" +
//            "8128376 30\n" +
//            "259694 2\n" +
//            "10267200 2\n" +
//            "591548 2\n" +
//            "5755696 2\n" +
//            "4307513 2\n" +
//            "5863522 2\n" +
//            "10040589 1\n" +
//            "2234412 1\n" +
//            "5086932 1\n" +
//            "14706276 1\n" +
//            "15430629 2\n" +
//            "2150128 2\n" +
//            "14561793 1\n" +
//            "7991506 2\n" +
//            "824138 2\n" +
//            "3450600 2\n" +
//            "6482303 1\n" +
//            "11413148 1\n" +
//            "12215231 2\n" +
//            "7578498 1\n" +
//            "13184008 2\n" +
//            "6684996 1\n" +
//            "11579040 1\n" +
//            "2662824 1\n" +
//            "13334004 2\n" +
//            "5954542 1\n" +
//            "7364389 1\n" +
//            "8028062 1\n" +
//            "11858536 1\n" +
//            "15223536 2");


    static int ni() {
        return sc.nextInt();
    }

    static int[] nia(int l) {
        int[] r = new int[l];
        for (int s = 0; s < l; s++) {
            r[s] = ni();
        }
        return r;
    }


    public static void main(String[] args) {
        boolean multi = false;

        if (multi) {
            int n = ni();
            for (int i = 0; i < n; i++) {
                solve(i + 1);
            }
        } else {
            solve(1);
        }

    }

    static long [] mm;
    static long nn;
    private static void solve(int csn) {
        int n = ni();
        Map<Integer, Long>[] dr = new Map[n];
        for (int l = 0 ; l < n ; l++) {
            dr[l] = new HashMap<>();
        }
        for (int s = 0; s < n - 1; s++) {
            int l = ni() - 1;
            int r = ni() - 1;
            dr[l].put(r, 1L << s);
            dr[r].put(l, 1L << s);
        }
        nn = n - 1;
        int m = ni();
        mm = new long[m];
        boolean [] visited = new boolean[n];
        for (int s = 0 ; s < m ; s++) {
            int f = ni() - 1;
            int t = ni() - 1;
            Arrays.fill(visited, false);
            visited[f] = true;
            mm[s] = dfs(f, t, visited, dr);
        }
        System.out.println(slv(m - 1, 0L));
    }

    private static long slv(int lastInd, long mask) {
        if ((mm[lastInd] | mask) == mask) {
            return 0;
        }
        if (lastInd == 0) {
            int common = Long.bitCount(mask & mm[0]);

            return (1L << (nn - Long.bitCount(mask | mm[lastInd]))) * ( (1L << (Long.bitCount(mm[0]) - common)) - 1);
        }

        long a1 = slv(lastInd - 1, mask);
        long a2 = slv(lastInd - 1, mask | mm[lastInd]);
        return a1 - a2;
    }

    private static long dfs(int f, int t, boolean[] visited, Map<Integer, Long>[] dr) {
        if (f == t) return 0;
        for (Map.Entry<Integer, Long> edges : dr[f].entrySet()) {
            int k = edges.getKey();
            long mask = edges.getValue();
            if (!visited[k]) {
                visited[k] = true;
                long ans = dfs(k, t, visited, dr);
                if (ans >= 0) {
                    return mask | ans;
                }
            }


        }

        return -1;
    }

    private static void printArray(int[][] nd) {
        for (int[] k : nd) {
            for (int i : k) {
                System.out.print((i + 1) + " ");
            }
            System.out.println();
        }
    }

    private static void update(boolean[][] contains, int[] ints) {
        for (int s = 0; s < ints.length; s++) {
            contains[s][ints[s] / ints.length] = true;
        }
    }


    private static final int[] inn(int n) {
        int[] data = new int[n];
        Arrays.fill(data, -1);
        return data;
    }

    private static final int max(int[] n) {
        int max = 0;
        for (int i : n) {
            max = Math.max(i, max);
        }
        return max;
    }


}