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.BufferedReader;
import java.io.File;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class OnePointPathsLog {
    static final int jumps = 19;
    static int[][] parents;
    static int[] parent; // parents[0]
    static int[] deep;
    static int[] subTreeSize;
    static int[] subTree;
    static int[] extCount;
    static int vertices;

    static List<Set<Integer>> neibours;

    static int[] treeLine;
    static int tlc;


    static int jump(int a, int t) {
        for (int i = 0; i < jumps; ++i) {
            if (((1 << i) & t) != 0)
                a = parents[i][a];
        }
        return a;
    }

    static int lca(int a, int b) {
        if (deep[a] > deep[b]) a = jump(a, deep[a] - deep[b]);
        if (deep[a] < deep[b]) b = jump(b, deep[b] - deep[a]);
        if (a == b) return a;
        for (int i = jumps - 1; i >= 0; --i) {
            if (parents[i][a] != parents[i][b]) {
                a = parents[i][a];
                b = parents[i][b];
            }
        }
        return parent[a];
    }


    static class Path {
        int from;
        int to;
        int lca;
        int[] neibours;

        Path(int a, int b) {
            from = a;
            to = b;
            lca = lca(a, b);
            neibours = buildNeibours(a, b, lca);
        }

        private int[] buildNeibours(int a, int b, int c) {
            if(a==b) return new int[]{};
            if(a == c) return new int[]{jump(b, deep[b]-deep[c]-1)};
            if(b == c) return new int[]{jump(a, deep[a]-deep[c]-1)};
            int n1 = jump(b, deep[b]-deep[c]-1);
            int n2 = jump(a, deep[a]-deep[c]-1);
            return new int[]{Math.min(n1,n2),Math.max(n1, n2)};
        }

        public void update(int p, int v) {
            for(int i = 0; i<neibours.length;++i)
                if(neibours[i]==p)
                    neibours[i] = v;
        }
    }

    static int marker;
    static int smallPaths;
    private static long findOnes(int root,  List<Path> paths) {
        if (paths.isEmpty()) return 0;
        int n = subTreeSize[root];
      //  boolean type = false;
        //if (n>10000) {
          //  type = true;
          //  System.out.println(n);
        //}
        if (n == 1) {
            long p = paths.size();
            return p * (p - 1) / 2;
        }
        if (n == 2) {
            long t1 = 0;
            long t2 = 0;
            long t3 = 0;
            for (Path p : paths) {
                if (p.from != p.to) ++t3;
                else if (p.from == root) ++t1;
                else ++t2;
            }
            return t3 * (t1 + t2) + t1 * (t1 - 1) / 2 + t2 * (t2 - 1) / 2;
        }

        if(n<10) return findOnesDropRoot(root, paths);
        if(paths.size()<300) {
            ++smallPaths;
        }
        int child = maxChild(root);
        if(subTreeSize[child]*2 <= n) {
            //if(type) System.out.println("center");
            return findOnesDropRoot(root, paths);
        }
       // if(type) System.out.println("edge");
        while (subTreeSize[child]*3>n) child = maxChild(child);
        child = parent[child];
        int par = parent[child];

        List<Path> inner = new ArrayList<>();
        List<Path> outer = new ArrayList<>();


        int v = vertices++;
        if(v>=subTree.length) while (true);
        neibours.get(par).remove(child);
        neibours.get(par).add(v);
        subTreeSize[v] = 1;
        parent[v] = par;

        int d = subTreeSize[child] - 1;
        while (true) {
            subTreeSize[par]-=d;
            if(par == root) break;
            par = parent[par];
        }



        ++marker;
       expandTree(child);
       // markSubtree(child, marker);
        for(int i = 0; i<tlc; ++i) {
            extCount[treeLine[i]] = 0;
            subTree[treeLine[i]] = marker;
        }


        for(Path p: paths) {
            if(subTree[p.lca] == marker) {
                inner.add(p);
                continue;
            }
            if(subTree[p.from] == marker) {
                ++extCount[p.from];
                p.from = v;
                p.update(child, v);
            }
            if(subTree[p.to] == marker) {
                ++extCount[p.to];
                p.to = v;
                p.update(child, v);
            }
            outer.add(p);
        }
       // updateExtCount(child);
        for(int i = tlc-1; i>0; --i) {
            int j = treeLine[i];
            extCount[parent[j]]+=extCount[j];
        }

        long ans = 0;
        for(Path p: inner) {
            ans+=extCount[p.lca];
            for(int i: p.neibours) ans-=extCount[i];
        }
        return ans + findOnes(root, outer) + findOnes(child, inner);
    }


    private static int maxChild(int center) {

        return neibours.get(center).stream().mapToInt(i -> i)
                .reduce((a, b) -> subTreeSize[a] > subTreeSize[b] ? a : b)
                .getAsInt();

    }

    private static long findOnesDropRoot(int root, List<Path> paths) {
        List<Path> center = new ArrayList<>();
        Map<Integer, List<Path>> inner = new HashMap<>();
        Map<Integer, Integer> markers = new HashMap<>();
        expandTree(root);
        for(Integer i: neibours.get(root)) {
            int m = ++marker;
            markers.put(m, i);
            subTree[i] = m;
            extCount[i] = 0;
            inner.put(i, new ArrayList<>());
           // markSubtree(i, m);
        }
        for(int i = 1+markers.size(); i<tlc; ++i) {
            int v = treeLine[i];
            subTree[v] = subTree[parent[v]];
            extCount[v] = 0;
        }

        for(Path p: paths) {
            if(p.lca == root) {
                ++extCount[p.from];
                ++extCount[p.to];
                center.add(p);
            } else {
                inner.get(markers.get(subTree[p.from])).add(p);
            }
        }
        //updateExtCount(root);
        for(int i = tlc-1; i>0; --i) {
            int j = treeLine[i];
            extCount[parent[j]]+=extCount[j];
        }
        long ans = findOnes(center);
        for(Map.Entry<Integer, List<Path>> p: inner.entrySet()) {
            for(Path path: p.getValue()) {
                ans+=extCount[path.lca];
                for(int i: path.neibours) ans-=extCount[i];
            }
            ans+=findOnes(p.getKey(), p.getValue());
        }
        return ans;
    }

    static class PairCounter {
        Map<Integer, Integer> ones = new HashMap<>();
        Map<Long, Integer> pairs = new HashMap<>();

        int getAndAppend(int[] neibours) {
            if (neibours.length == 0) return 0;
            if (neibours.length == 1) {
                if (ones.containsKey(neibours[0])) {
                    int t = ones.get(neibours[0]);
                    ones.put(neibours[0], t + 1);
                    return t;
                } else {
                    ones.put(neibours[0], 1);
                    return 0;
                }
            }
            int t = getAndAppend(new int[]{neibours[0]}) + getAndAppend(new int[]{neibours[1]});
            long l = neibours[0] * 1000000L + neibours[1];
            if (pairs.containsKey(l)) {
                int k = pairs.get(l);
                t -= k;
                pairs.put(l, k + 1);
            } else {
                pairs.put(l, 1);
            }
            return t;
        }
    }

    private static long findOnes(List<Path> center) {
        int cnt = 0;
        long ans = 0;
        PairCounter pcn = new PairCounter();
        for (Path p : center) {
            ans += cnt - pcn.getAndAppend(p.neibours);
            ++cnt;
        }
        return ans;
    }

    static void expandTree(int vert) {
        tlc = 1;
        treeLine[0] = vert;
        for(int i = 0; i<tlc; ++i) {
            int v = treeLine[i];
            if (subTreeSize[v]>1)
                for(int j: neibours.get(v)) treeLine[tlc++] = j;
        }
    }

    private static void updateExtCount(int vert) {
        if(vert>=neibours.size()) return;
        for (int i : neibours.get(vert)) {
                updateExtCount(i);
                extCount[vert] += extCount[i];
            }
    }

    private static void markSubtree(int vert, int m) {

        subTree[vert] = m;
        extCount[vert] = 0;
        if(vert>=neibours.size()) return;

        for (int i : neibours.get(vert))
             markSubtree(i, m);
    }


    static BufferedReader input;
    static StringTokenizer stoken = new StringTokenizer("");
    static String nextString() throws IOException {
        while (!stoken.hasMoreTokens()){
            String st = input.readLine();
            stoken = new StringTokenizer(st);
        }
        return stoken.nextToken();
    }
    static int nextInt() throws Exception {
        return Integer.parseInt(nextString());
    }

    public static void main(String[] args) throws Exception{
        long l1 = System.currentTimeMillis();
        input = new BufferedReader(
                new InputStreamReader(System.in)
        );
        //Scanner scanner = // new Scanner(new File("bigtest3.txt"));
           //new Scanner(System.in);
        int n = /*scanner.*/nextInt();
        vertices = n;
        int nv = (int)(1.3*n);
        parents = new int[jumps][];
        parent = new int[nv];
        parents[0] =  parent;
        for(int i = 1; i<jumps; ++i) parents[i] = new int[n];
        deep = new int[n];
        subTreeSize = new int[nv];
        subTree = new int[nv];
        extCount = new int[nv];
        treeLine = new int[nv];

        neibours = IntStream.range(0, n).mapToObj(i -> new HashSet<Integer>()).collect(Collectors.toList());


        for (int i = 1; i < n; ++i) {
            int a = /*scanner.*/nextInt() - 1;
            int b = /*scanner.*/nextInt() - 1;
            neibours.get(a).add(b);
            neibours.get(b).add(a);
        }
        initDSP(0, 0, 0);
        for (int i = 1; i < jumps; ++i)
            for (int j = 0; j < n; ++j)
                parents[i][j] = parents[i - 1][parents[i - 1][j]];

        for(int i = 0; i<n; ++i) neibours.get(i).remove(parent[i]);

        List<Path> paths = new ArrayList<>();
        int m = /*scanner.*/nextInt();
        for(int i = 0; i<m; ++i) paths.add(new Path(/*scanner.*/nextInt()-1, /*scanner.*/nextInt() - 1));

        System.out.println(findOnes(0, paths));
        //System.out.println(System.currentTimeMillis() - l1);
        //System.out.println(vertices);
        //System.out.println(smallPaths);
    }

    private static void initDSP(int vert, int prev, int d) {
        parent[vert] = prev;
        deep[vert] = d++;
        subTreeSize[vert] = 1;
        for (int i : neibours.get(vert))
            if (i != prev) {
                initDSP(i, vert, d);
                subTreeSize[vert] += subTreeSize[i];
            }
    }
}
