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.
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <cstring>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <functional>
#include <ctime>
#include <sstream>
#include <array>
#include <iomanip>
#include <random>

using namespace std;
typedef long long Long;
typedef long double Double;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<Long> VL;
typedef vector<VL> VVL;
typedef pair<int,int> PII;
typedef pair<Long,Long> PLL;

int read(int &x) { return scanf("%d", &x); }
int read(int &x, int &y) { return scanf("%d%d", &x, &y); }
int read(int &x, int &y, int &z) { return scanf("%d%d%d", &x, &y, &z); }
int read(Long &x) { return scanf("%lld", &x); }
int read(Long &x, Long &y) { return scanf("%lld%lld", &x, &y); }
int read(double &x) { return scanf("%lf", &x); }
char buff[2000010];
int read(string &s) { int r = scanf("%s", buff); s = buff; return r; }

#define dlog2(n) ((n) == -1 ? 0 : (31-__builtin_clz(n)))

using namespace std;

Long D[300010]; // this distance is optional
int ST[300010], EN[300010], GID = 0;
struct BinaryLifting {
    VVI adj, T;
    VI L;
    int N;
    BinaryLifting(int N) : N(N), adj(N), T(20, VI(N, -1)), L(N) { }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void build(int root = 0) {
        dfs(root);
        for (int i = 1; i < 20; ++i)
            for (int j = 0; j < N; ++j)
                if (T[i-1][j] != -1)
                    T[i][j] = T[i-1][ T[i-1][j] ];
    }
    void dfs(int u, int p = -1, int lvl = 0, Long v = 0) {
        T[0][u] = p; L[u] = lvl;
        ST[u] = GID++;
        D[u] += v; // add distance from root to have sum([v, root])
        for (int v : adj[u]) if (v != p) dfs(v, u, lvl+1, D[u]);
        EN[u] = GID - 1;
    }
    int lca(int u, int v) {
        if (L[u] < L[v]) swap(u, v);
        for (int i = 19; i >= 0; --i)
            if (L[u] - (1<<i) >= L[v])
                u = T[i][u];
        if (u == v) return u;
        for (int i = 19; i >= 0; --i)
            if (T[i][u] != T[i][v])
                u = T[i][u], v = T[i][v];
        return T[0][u];
    }
    int lift(int u, int x) {
        for (int i = 19; i >= 0; --i)
            if ((1<<i) & x)
                u = T[i][u], x -= (1<<i);
        return u;
    }
    Long cost(int u, int p) { // from [u, p)
        return D[u] - (p == -1 ? 0 : D[p]);
    }
};

struct Fenwick {
    vector<Long> V;
    int hb;
    Fenwick(int N) : V(N+10) {
        hb = 1;
        while (hb*2 < V.size()) hb <<= 1;
    }
    void add(int x, Long v) {
        for (int i = x + 1; i < V.size(); i += (i & -i)) {
            V[i] += v;
        }
    }
    Long get(int x) {
        Long r = 0;
        for (int i = x + 1; i > 0; i -= (i & -i)) {
            r += V[i];
        }
        return r;
    }
    // V.size() - 1 if not found
    Long lowerBound(Long val) {
        int ans = 0;
        for (int i = hb; i > 0; i >>= 1) {
            int nans = ans | i;
            if (nans < V.size() && V[nans] < val) {
                ans = nans;
                val -= V[ans];
            }
        }
        return ans;
    }
    Long segSum(int i, int j) {
        return get(j) - get(i-1);
    }
};

vector<PII> paths[300010];
Fenwick FT(300010);

void dfs(int u, int p, BinaryLifting &BL, Long &ans) {
    map<int, int> doublePathsGoingToX; //          .... r ---- x
    map<int, int> singlePathsGoingToX; //            r ---- x
    map<PII, int> doublePathsGoingToXAndY; // x ---- r ---- y
    int totSinglePaths = 0, totDoublePaths = 0, totSingleNodePaths = 0;
    for (auto path : paths[u]) {
        if (path.first == u && path.second == u) {
            totSingleNodePaths++;
        } else if (path.first == u || path.second == u) {
            if (path.second == u) swap(path.first, path.second);
            int ps = BL.lift(path.second, BL.L[path.second] - BL.L[u] - 1);
            singlePathsGoingToX[ps]++;
            totSinglePaths++;
        } else {
            int pf = BL.lift(path.first, BL.L[path.first] - BL.L[u] - 1);
            int ps = BL.lift(path.second, BL.L[path.second] - BL.L[u] - 1);
            doublePathsGoingToX[pf]++;
            doublePathsGoingToX[ps]++;
            totDoublePaths++;
            doublePathsGoingToXAndY[PII(min(pf, ps), max(pf, ps))]++;
        }
    }
    {
        int t = FT.segSum(ST[u], ST[u]);
        singlePathsGoingToX[p] += t;
        totSinglePaths += t;
    }
    for (int v : BL.adj[u]) {
        if (v == p) continue;
        int t = FT.segSum(ST[v], EN[v]);
        if (t == 0) continue;
        doublePathsGoingToXAndY[PII(min(p, v), max(p, v))] += t;
        doublePathsGoingToX[p] += t;
        doublePathsGoingToX[v] += t;
        totDoublePaths += t;
    }
    ans += 1LL * totSingleNodePaths * (totSinglePaths + totDoublePaths) + 1LL*totSingleNodePaths*(totSingleNodePaths-1)/2;
    for (auto s : singlePathsGoingToX) {
        totSinglePaths -= s.second;
        ans += 1LL * s.second * (totSinglePaths + totDoublePaths - doublePathsGoingToX[s.first]);
    }
    for (auto s : doublePathsGoingToXAndY) {
        totDoublePaths -= s.second;
        doublePathsGoingToX[s.first.first] -= s.second;
        doublePathsGoingToX[s.first.second] -= s.second;
        ans += 1LL * s.second * (totDoublePaths - doublePathsGoingToX[s.first.first] - doublePathsGoingToX[s.first.second]);
    }
    for (auto path : paths[u]) {
        FT.add(ST[path.first], +1);
        FT.add(ST[path.second], +1);
    }
    for (int v : BL.adj[u]) {
        if (v == p) continue;
        dfs(v, u, BL, ans);
    }
}


int main(){


    int TC = 1;
//    read(TC);
    while (TC-->0) {

        int N;
        read(N);
        BinaryLifting BL(N);
        for (int i = 0; i < N-1; ++i) {
            int u, v;
            read(u, v);
            u--;v--;
            BL.addEdge(u, v);
        }
        BL.build();

        int M;
        read(M);
        for (int i = 0; i < M; ++i) {
            int u, v;
            read(u, v);
            u--;v--;
            if (BL.L[u] > BL.L[v]) swap(u, v);
            int l = BL.lca(u, v);
            paths[l].push_back(PII(u, v));
        }
        Long ans = 0;
        dfs(0, -1, BL, ans);
        cout << ans << endl;


    }


}