You are given a tree consisting of n vertices, and m simple vertex paths. Your task is to find how many pairs of those paths intersect at exactly one vertex. More formally you have to find the number of pairs (i, j) (1 ≤ i < j ≤ m) such that path_i and path_j have exactly one vertex in common. 

Input

First line contains a single integer n (1 ≤ n ≤ 3 ⋅ 10^5).

Next n - 1 lines describe the tree. Each line contains two integers u and v (1 ≤ u, v ≤ n) describing an edge between vertices u and v.

Next line contains a single integer m (1 ≤ m ≤ 3 ⋅ 10^5).

Next m lines describe paths. Each line describes a path by it's two endpoints u and v (1 ≤ u, v ≤ n). The given path is all the vertices on the shortest path from u to v (including u and v).

Output

Output a single integer — the number of pairs of paths that intersect at exactly one vertex.

Examples

Input


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


Output


2


Input


1
3
1 1
1 1
1 1


Output


3


Input


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


Output


7

Note

<image>

The tree in the first example and paths look like this. Pairs (1,4) and (3,4) intersect at one vertex.

In the second example all three paths contain the same single vertex, so all pairs (1, 2), (1, 3) and (2, 3) intersect at one vertex.

The third example is the same as the first example with two additional paths. Pairs (1,4), (1,5), (2,5), (3,4), (3,5), (3,6) and (5,6) intersect at one vertex.
/**
 * author: derrick20
 * created: 2/20/21 10:47 PM
 */
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class PairOfPaths {
    static FastScanner sc = new FastScanner();
    static PrintWriter out = new PrintWriter(System.out);
    
    public static void main(String[] args) {
        N = sc.nextInt();
        adjList = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            adjList[i] = new ArrayList<>();
        }
        for (int i = 0; i < N - 1; i++) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            adjList[u].add(v);
            adjList[v].add(u);
        }
        setupLCA();
        subtree = new long[N];
        nonLCA = new long[N];
        outside = new HashMap[N];
        Arrays.setAll(outside, i -> new HashMap<>());
        duplicates = new HashMap[N];
        Arrays.setAll(duplicates, i -> new HashMap<>());
        up = new long[N];
        int M = sc.nextInt();
        for (int p = 0; p < M; p++) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            int lca = leastCommonAncestor(u, v);
            for (int node : new int[]{u, v}) {
                if (node != lca) {
                    int anc = lastBelow(node, lca);
                    nonLCA[node]++;
                    outside[lca].merge(anc, 1L, Long::sum);
                    up[node]++;
                    up[anc]--;
                }
            }
            subtree[lca]++;
            if (u != lca && v != lca) {
                // must be from different subtrees, identify with child node
                int ancU = lastBelow(u, lca);
                int ancV = lastBelow(v, lca);
                if (ancU != ancV) {
                    duplicates[lca].merge(new Pair(ancU, ancV), 1L, Long::sum);
                }
            }
        }
        propagate(0, -1);
        long ans = 0;
        for (int lca = 0; lca < N; lca++) {
            long allPairs = subtree[lca] * (subtree[lca] - 1) / 2;
            long upward = subtree[lca] * nonLCA[lca];
            // two ways for us to include an upward path:
            // either use a non-lca path starting at this lca
            // or, use something that starts in a child branch and goes up
            long overCounted = 0;
            for (int adj : adjList[lca]) {
                if (adj != firstParents[lca]) {
                    long outPaths = outside[lca].getOrDefault(adj, 0L);
                    upward += up[adj] * (subtree[lca] - outPaths);
//                    System.out.println("For adj = " + adj + " outpaths = " + outPaths);
                    overCounted += outPaths * (outPaths - 1) / 2;
                }
            }
            long underCounted = 0;
            for (long dup : duplicates[lca].values()) {
                underCounted += dup * (dup - 1) / 2;
            }
            long downward = allPairs - overCounted + underCounted;
//            System.out.println(downward + " " + upward);
            ans += downward + upward;
        }
        out.println(ans);
        out.close();
    }
/*
8
1 2
2 3
3 4
4 5
4 6
5 7
6 8
5
7 8
7 8
1 4
1 4
1 4
 */

    static int N;
    static int maxDepth;
    static int[] depth;
    static int[][] parent;
    static int[] firstParents;
    static ArrayList<Integer>[] adjList;

    static long[] subtree, nonLCA, up;
    static HashMap<Integer, Long>[] outside;
    static HashMap<Pair, Long>[] duplicates;

    static void propagate(int node, int par) {
        for (int adj : adjList[node]) {
            if (adj != par) {
                propagate(adj, node);
                up[node] += up[adj];
            }
        }
    }

    static class Pair {
        int u, v;
        public Pair(int uu, int vv) {
            u = min(uu, vv); v = max(uu, vv);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair pair = (Pair) o;
            return u == pair.u && v == pair.v;
        }

        @Override
        public int hashCode() {
            return Objects.hash(u, v);
        }
    }

    static int lastBelow(int curr, int goal) {
        for (int k = parent.length - 1; k >= 0; k--) {
            if (depth[parent[k][curr]] > depth[goal]) {
                curr = parent[k][curr];
            }
        }
        ASSERT(firstParents[curr] == goal);
        return curr;
    }

    static void setupLCA() {
        maxDepth = 0;
        depth = new int[N];
        firstParents = new int[N];
        firstParents[0] = 0;
        depth[0] = 0;
        dfs(0);
        int power = 1;
        while (1 << power <= maxDepth) {
            power++;
        }
        parent = new int[power][N];
        for (int node = 0; node < N; node++) {
            parent[0][node] = firstParents[node];
        }
        for (int p = 1; p < parent.length; p++) {
            for (int i = 0; i < N; i++) {
                parent[p][i] = -1;
            }
        }
        for (int p = 1; p < parent.length; p++) {
            for (int node = 0; node < N; node++) {
                if (parent[p - 1][node] != -1) {
                    int myParent = parent[p - 1][node];
                    parent[p][node] = parent[p-1][myParent];
                }
            }
        }
    }

    static void dfs(int node) {
        for (int adj : adjList[node]) {
            if (adj != firstParents[node]) {
                firstParents[adj] = node;
                depth[adj] = depth[node] + 1;
                maxDepth = Math.max(maxDepth, depth[adj]);
                dfs(adj);
            }
        }
    }

    static int leastCommonAncestor(int a, int b) {
        if (depth[b] > depth[a]) {
            int c = a;
            a = b;
            b = c;
        }
        int dist = depth[a] - depth[b];
        while (dist > 0) {
            int power = (int) (Math.log(dist) / Math.log(2));
            a = parent[power][a];
            dist -= 1 << power;
        }
        if (a == b) {
            return a;
        }
        for (int j = parent.length - 1; j >= 0; j--) {
            if (parent[j][a] != parent[j][b]) {
                a = parent[j][a];
                b = parent[j][b];
            }
        }
        return parent[0][a];
    }

    static class FastScanner {
        private int BS = 1 << 16;
        private char NC = (char) 0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;
    
        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }
    
        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            } catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }
    
        char getChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }
    
        int nextInt() {
            return (int) nextLong();
        }
    
        long nextLong() {
            cnt = 1;
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = getChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                cnt *= 10;
            }
            return neg ? -res : res;
        }
    
        double nextDouble() {
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            double cur = nextLong();
            if (c != '.') {
                return neg ? -cur : cur;
            } else {
                double frac = nextLong() / cnt;
                return neg ? -cur - frac : cur + frac;
            }
        }
    
        String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c > 32) {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }
    
        String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c != '\n') {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }
    
        boolean hasNext() {
            if (c > 32) return true;
            while (true) {
                c = getChar();
                if (c == NC) return false;
                else if (c > 32) return true;
            }
        }
    }
    
    static void ASSERT(boolean assertion, String message) {
        if (!assertion) throw new AssertionError(message);
    }
    
    static void ASSERT(boolean assertion) {
        if (!assertion) throw new AssertionError();
    }
}