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

/*
polyakoff
*/

public class Main {

    static FastReader in;
    static PrintWriter out;
    static Random rand = new Random();
    static final int oo = (int) 1e9 + 10;
    static final long OO = (long) 2e18 + 10;
    static final int MOD = (int) 1e9 + 7;
    static final int LOGN = 22;

    static int n, m;
    static ArrayList<Integer>[] g;
    static int[][] paths, par, childs, cntDown1, cntUp2;
    static int[] tin, tout, cntUp1;
    static ArrayList<Pair>[] forks;
    static HashMap<Long, Integer>[] cntDown2;

    static class Pair {
        int i1, i2;
        Pair(int i1, int i2) {
            this.i1 = i1;
            this.i2 = i2;
        }
    }

    static int timer = 0;
    static void dfs0(int v, int from) {
        tin[v] = timer++;
        par[v][0] = from;
        for (int i = 1; i < LOGN; i++) {
            par[v][i] = par[par[v][i - 1]][i - 1];
        }
        for (int to : g[v]) {
            if (to == from)
                continue;
            dfs0(to, v);
        }
        tout[v] = timer++;
    }

    static boolean isAncestor(int v, int u) {
        return tin[v] < tin[u] && tout[u] < tout[v];
    }

    static int lca(int v, int u) {
        if (v == u) return v;
        if (isAncestor(v, u)) return v;
        if (isAncestor(u, v)) return u;
        for (int i = LOGN - 1; i >= 0; i--) {
            if (!isAncestor(par[v][i], u))
                v = par[v][i];
        }
        return par[v][0];
    }

    // get index of child in which tree u is
    static int getChild(int v, int u) {
        int low = 0, high = childs[v].length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (childs[v][mid] == u || isAncestor(childs[v][mid], u))
                return mid;
            if (tout[childs[v][mid]] < tin[u])
                low = mid + 1;
            else
                high = mid - 1;
        }
        return low;
    }

    static void dfs1(int v, int from) {
        int i = 0;
        for (int to : g[v]) {
            if (to == from)
                continue;
            dfs1(to, v);
            cntUp1[v] += cntUp1[to];
            cntUp2[v][i++] = cntUp1[to];
        }
        for (Pair p : forks[v]) {
            if (p.i1 != -1) {
                cntUp1[v]--;
                cntUp2[v][p.i1]--;
            }
            if (p.i2 != -1) {
                cntUp1[v]--;
                cntUp2[v][p.i2]--;
            }
        }
    }

    static void solve() {
        n = in.nextInt();
        g = new ArrayList[n]; Arrays.setAll(g, i -> new ArrayList<>());
        for (int i = 0; i < n - 1; i++) {
            int v = in.nextInt() - 1;
            int u = in.nextInt() - 1;
            g[v].add(u);
            g[u].add(v);
        }
        m = in.nextInt();
        paths = new int[m][3];
        for (int i = 0; i < m; i++) {
            int v = in.nextInt() - 1;
            int u = in.nextInt() - 1;
            paths[i][0] = v;
            paths[i][1] = u;
        }

        par = new int[n][LOGN];
        tin = new int[n];
        tout = new int[n];
        dfs0(0, 0);

        childs = new int[n][];
        childs[0] = new int[g[0].size()];
        for (int i = 1; i < n; i++) {
            childs[i] = new int[g[i].size() - 1];
        }
        forks = new ArrayList[n]; Arrays.setAll(forks, i -> new ArrayList<>());
        cntDown1 = new int[n][]; Arrays.setAll(cntDown1, i -> new int[childs[i].length]);
        cntDown2 = new HashMap[n]; Arrays.setAll(cntDown2, i -> new HashMap<>());
        for (int v = 0; v < n; v++) {
            int i = 0;
            for (int to : g[v]) {
                if (to == par[v][0])
                    continue;
                childs[v][i++] = to;
            }
        }

        // prepare for same lca
        for (int i = 0; i < m; i++) {
            int v = paths[i][0];
            int u = paths[i][1];
            int lca = lca(v, u);
            paths[i][2] = lca;
            if (v == u) {
                forks[v].add(new Pair(-1, -1));
                continue;
            }
            // indices of childs where v and u are
            int i1 = lca != v ? getChild(lca, v) : -1;
            int i2 = lca != u ? getChild(lca, u) : -1;
            if (i2 < i1) {
                int temp = i1;
                i1 = i2;
                i2 = temp;
            }
            forks[lca].add(new Pair(i1, i2));
            if (i1 != -1)
                cntDown1[lca][i1]++;
            if (i2 != -1)
                cntDown1[lca][i2]++;
            if (i1 != -1 && i2 != -1) {
                long hash = 1L * i1 * childs[lca].length + i2;
                cntDown2[lca].putIfAbsent(hash, 0);
                cntDown2[lca].put(hash, cntDown2[lca].get(hash) + 1);
            }
        }

        // prepare for different lca
        cntUp1 = new int[n];
        cntUp2 = new int[n][]; Arrays.setAll(cntUp2, i -> new int[childs[i].length]);
        for (int i = 0; i < m; i++) {
            int v = paths[i][0];
            int u = paths[i][1];
            int lca = paths[i][2];
            if (v != lca)
                cntUp1[v]++;
            if (u != lca)
                cntUp1[u]++;
        }
        dfs1(0, 0);

        long ans = 0;
        for (int v = 0; v < n; v++) {
            int total = forks[v].size();
            long cnt = 1L * total * (total - 1);
            for (Pair p : forks[v]) {
                if (p.i1 != -1)
                    cnt -= cntDown1[v][p.i1] - 1;
                if (p.i2 != -1)
                    cnt -= cntDown1[v][p.i2] - 1;
                if (p.i1 != -1 && p.i2 != -1) {
                    long hash = 1L * p.i1 * childs[v].length + p.i2;
                    cnt += cntDown2[v].get(hash) - 1;
                }
            }
            cnt /= 2;
            ans += cnt;
        }

        for (int v = 0; v < n; v++) {
            for (Pair p : forks[v]) {
                long cnt = cntUp1[v];
                if (p.i1 != -1)
                    cnt -= cntUp2[v][p.i1];
                if (p.i2 != -1)
                    cnt -= cntUp2[v][p.i2];
                ans += cnt;
            }
        }

        out.println(ans);

    }

    public static void main(String[] args) {
        in = new FastReader();
        out = new PrintWriter(System.out);

        int T = 1;
//        T = in.nextInt();
        while (T-- > 0)
            solve();

        out.flush();
        out.close();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader() {
            this(System.in);
        }
        FastReader(String file) throws FileNotFoundException {
            this(new FileInputStream(file));
        }
        FastReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String next() {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(nextLine());
            }
            return st.nextToken();
        }
        String nextLine() {
            String line;
            try {
                line = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return line;
        }
    }
}