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 <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "../../debug.h"
#else
#define DEB(...)
#endif
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define endl '\n'
#define all(a) (a).begin(),(a).end()
#define sz(a) ((int)(a).size())
#define forn(i,n) for(int i=0; i<(n); i++)
#define forne(i,n) for(int i=0; i<(n) || (cout << endl,0) ; i++) 
#define fora(i,a,b) for(int i=a; i<=(b); i++)
#define ford(i,a,b) for(int i=a; i>=(b); i--)
#define muniq(x) sort(all(x)), x.erase(unique(all(x)), x.end())
template<class T> bool mmin(T& a, const T& b) { return b<a?a=b,1:0; }
template<class T> bool mmax(T& a, const T& b) { return a<b?a=b,1:0; }
template<class T> void puts(T a) { cout << a << ' '; }
template<class T> void put(T a) { cout << a << endl; }
template<class T> void put(T ita, T itb) { while(ita!=itb) puts(*ita++); cout << endl; }
void yesno(bool c) { put(c?"YES":"NO"); }
void yes() { yesno(true); } void no() { yesno(false); }
void imp() { put("-1"); }
const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3f;
 
// -------------------------------------
 
struct base_graph {
    int n, ecnt = 0;
    vector<int> from,to;
 
    base_graph(int n) : n(n) {}
 
    void reserve(int m) {
        from.reserve(m);
        to.reserve(m);
    }
 
    virtual int add(int a, int b) {
        assert(0 <= a && a < n);
        assert(0 <= b && b < n);
        from.push_back(a); to.push_back(b);
        return ecnt++;
    }
};
 
struct dir_graph : public base_graph {
    vector<vector<pair<int,int>>> out,in;
 
    dir_graph(int n) : base_graph(n), out(n), in(n) {}
 
    int add(int a, int b) {
        int e = base_graph::add(a,b);
        out[a].push_back({e,b});
        in[b].push_back({e,a});
        return e;
    }
};
 
struct undir_graph : public base_graph {
    vector<vector<pair<int,int>>> edg;
 
    undir_graph(int n) : base_graph(n), edg(n) {}
 
    int add(int a, int b)  {
        if(b>a) swap(a,b);
        int e = base_graph::add(a,b);
        edg[a].push_back({e,b});
        edg[b].push_back({e,a});
        return e;
    }
};
 
// -------------------------------------
 
template<class T, class G> 
struct weightable : public G {
    vector<T> w;
 
    weightable(int n) : G(n) {}
 
    using G::add;
 
    int add(int a, int b, T ww) {
        w.push_back(ww);
        return G::add(a,b);
    }
 
    void reserve(int m) {
        G::reserve(m);
        w.reserve(m);
    }
};
 
template<class T> using wdir_graph = weightable<T,dir_graph>;
template<class T> using wundir_graph = weightable<T,undir_graph>;
 
// -------------------------------------
 
void readin(base_graph& g, int m, int offset = 1) {
    g.reserve(m);
    for(int i=0; i<m; i++) {
        int a, b;
        cin >> a >> b;
        a -= offset;
        b -= offset;
        g.add(a,b);
    }
}
 
template<class T, class G>
void readinw(weightable<T,G>& g, int m, int offset = 1) {
    g.reserve(m);
    for(int i=0; i<m; i++) {
        int a, b; T ww = 0;
        cin >> a >> b >> ww;
        a -= offset;
        b -= offset;
        g.add(a,b,ww);
    }
}
 
void readin_tree_format(base_graph& g, int offset = 1) {
    g.reserve(g.n-1);
    for(int i=2; i<=g.n; i++) {
        int p; cin >> p;
        int a = i-offset;
        p -= offset;
        g.add(a,p);
    }
}
 
// ---------------------------------------------
// ---------------------------------------------
 
// confirmed in contest
struct binary_lifting {
    const int mxw = 20;
    vector<int> dep;
    vector<vector<int>> par;
 
    binary_lifting(undir_graph& g) : dep(g.n), par(g.n,vector<int>(mxw,-1)) {  // assumes 0-index of nodes
        function<void(int,int,int)> dfs = [&](int u, int p, int d) {
            dep[u] = d;
            int pp = p;
            for(int k=0; k<mxw && pp>=0; k++) {
                par[u][k] = pp;
                pp = par[pp][k];
            }
 
            for(auto [e,v] : g.edg[u]) 
                if(v!=p) dfs(v,u,d+1);
        };
        dfs(0,-1,0);
    }
 
// -----------------------------------
 
    //  not confirmed in contest
    int fast_bin_search(int u, bool (*f)(int v)) {
        for(int i=mxw-1; i>=0; i--) {
            if(par[u][i] && f(par[u][i]))
                u = par[u][i];
        }
 
        // nodes (not) fulfilling criterion on path in tree:       
        //         <- root   ...   leaf ->
        // ...   par[u][0]    |   u             ...
        // ...   !f           |   f     ...
 
        return u;
    }
 
// -----------------------------------
 
    int walkup(int u, int h) {
        assert(h<=dep[u]);
        int i = 0;
        while(h) {
//            DEB(u,h);
//            assert(u>=0);
            if(h&1) u = par[u][i];
            i++;
            h = h>>1;
        }
        return u;
    }
 
    int lca(int a, int b) {
        if(dep[a]<dep[b])
            swap(a,b);
        a = walkup(a,dep[a]-dep[b]);
 
        if(a==b) return a;
 
        // fast binary search
        for(int i=mxw-1; i>=0; i--) {
            if(par[a][i]!=par[b][i]) {
                a = par[a][i];
                b = par[b][i];
            }
        }
 
        return par[a][0];
    }
};
 
// ---------------------------------------------
 
void solve() {
    int n; cin >> n;
    undir_graph g(n);
    readin(g,n-1);
 
    binary_lifting bin(g);
 
    int m; cin >> m;
 
    vector<vector<pii>> subs(n);
    vi bot(n);
 
    forn(i,m) {
        int u,v;
        cin >> u >> v;
        u--; v--;
        if(u==v) {
            subs[u].pb({-1,-1});
        } else {
            int lca = bin.lca(u,v);
            if(lca==v) swap(u,v);
            if(lca==u) {
                bot[v]++;
                int vnx = bin.walkup(v,bin.dep[v] - bin.dep[lca] - 1);
                subs[lca].pb({-1,vnx});
            } else {
                bot[u]++; bot[v]++;
                int unx = bin.walkup(u,bin.dep[u] - bin.dep[lca] - 1);
                int vnx = bin.walkup(v,bin.dep[v] - bin.dep[lca] - 1);
                if(unx>vnx) swap(unx,vnx);
                subs[lca].pb({unx,vnx});
            }
        }
    }
 
    ll ans = 0;
 
    function<int(int,int)> dfs = [&](int u, int p) {
        ll tot = subs[u].size();
        ans += tot * (tot - 1) / 2;
 
        unordered_map<int,ll> mp;
        map<pii,ll> mp2;
        for(auto [l,r] : subs[u]) {
            if(l==r) continue;
            mp[l]++; mp[r]++;
            if(l!=-1) ans += mp2[{l,r}]++;
        }
 
        for(auto [p,c] : mp) {
            if(p==-1) continue;
            ans -= c * (c - 1) / 2;
        }
 
        int cntbot = 0;
        for(auto [e,v] : g.edg[u]) {
            if(v==p) continue;
            int nxcnt = dfs(v,u);
            ans += (tot - mp[v]) * (nxcnt - mp[v]);
            cntbot += nxcnt - mp[v];
        }
 
        ans += bot[u] * tot;
        return cntbot + bot[u];
    };
    dfs(0,-1); 
 
    put(ans);
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int tc = 1; //cin >> tc;
    while(tc--) solve();
 
    return 0;
}
