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.math.BigInteger;
import java.util.*;

public class Main implements Runnable {

    private static int MOD = 1_000_000_007;

    public static void main(String[] args) {
        // Run with 32MB stack
        Thread thread = new Thread(null, new Main(), "", 32 * 1024 * 1024);
        thread.start();
    }

    @Override
    public void run() {
        final Scanner scanner = new Scanner(System.in);
        solve(scanner);
    }

    static List<Edge>[] edges;

    static long es;
    static boolean getEdgeSet(int from, int to, int par) {
        if (from == to) {
            es = 0;
            return true;
        }
        for (Edge e: edges[from]) {
            if (e.to == par) continue;
            if (getEdgeSet(e.to, to, from)) {
                es |= 1L << e.id;
                return true;
            }
        }
        return false;
    }

    static class Edge {
        int to;
        int id;

        public Edge(int to, int id) {
            this.to = to;
            this.id = id;
        }
    }
    static void solve(Scanner scanner) {
        int N = Integer.parseInt(scanner.next());
        edges = new List[N];
        for (int i = 0; i < N; i++) {
            edges[i] = new ArrayList<>();
        }

        for (int i = 0; i < N - 1; i++) {
            int a = Integer.parseInt(scanner.next()) - 1;
            int b = Integer.parseInt(scanner.next()) - 1;
            edges[a].add(new Edge(b, i));
            edges[b].add(new Edge(a, i));
        }

        int M = Integer.parseInt(scanner.next());
        long[] edgeSet = new long[M];
        for (int i = 0; i < M; i++) {
            int a = Integer.parseInt(scanner.next()) - 1;
            int b = Integer.parseInt(scanner.next()) - 1;
            getEdgeSet(a, b, -1);
            edgeSet[i] = es;
        }

        long ans = 0;
        for (int i = 0; i < 1 << M; i++) {
            long activeEdges = 0;
            for (int j = 0; j < M; j++) {
                if ((i & (1L << j)) > 0) {
                    activeEdges |= edgeSet[j];
                }
            }
            long white = Long.bitCount(activeEdges);
            long cnt = 1L << (N - 1 - white);
            if (Integer.bitCount(i) % 2 == 0) {
                ans += cnt;
            } else {
                ans -= cnt;
            }
        }

        System.out.println(ans);
    }
}