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.
//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("-Ofast", "-funroll-all-loops", "-ffast-math")
//~ #pragma GCC target ("avx2")
//~ #pragma GCC
// target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") ~
// 火影三板斧
// #pragma GCC target ("avx2,fma")
// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

#include <algorithm>
#include <cassert>
#include <functional>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
using LL = long long;
#define int LL
#define eps 1e-8
#define fi first
#define se second
// #define endl '\12'
#define eb emplace_back
#define SZ(a) int32_t(a.size())
#define ALL(x) (x).begin(), (x).end()
#define trav(a, x) for (auto &a : x)
#define LOG(FMT...) fprintf(stderr, FMT)
#define close                                                         \
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr), \
        cout << fixed << setprecision(10)
#define FOR(i, x, y) for (LL i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (LL i = (x), _##i = (y); i > _##i; --i)
#define SORT_UNIQUE(c)         \
    (sort(c.begin(), c.end()), \
     c.resize(distance(c.begin(), unique(c.begin(), c.end()))))
#define CASET    \
    int ___T;    \
    cin >> ___T; \
    for (int __CS = 1; __CS <= ___T; __CS++)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
constexpr int mod = 1e9 + 7;  // 998244353
// mt19937 dlsrand(random_device{}());
// mt19937 mrand( chrono::system_clock::now().time_since_epoch().count());
// int rnd(int x) { return mrand() % x;}
// ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll ex_gcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    ll ret = ex_gcd(b, a % b, y, x);
    y -= a / b * x;
    return ret;
}
LL mul(LL u, LL v, LL p) {
    return (u * v - LL((long double)u * v / p) * p + p) % p;
}
LL bin(int x, LL n, LL MOD) {
    LL ret = MOD != 1;
    for (x %= MOD; n; n >>= 1, x = x * x % MOD)
        if (n & 1) ret = ret * x % MOD;
    return ret;
}
int norm(int x) { return x >= mod ? (x - mod) : x; }
inline LL get_inv(int x, LL p) { return bin(x, p - 2, p); }
inline ll get_inv(ll a) {
    ll x, y;
    ex_gcd(a, mod, x, y);
    return norm(x + mod);
}
template <class T>
inline void umin(T &x, T y) {
    x = x > y ? y : x;
}
template <class T>
inline void umax(T &x, T y) {
    x = x < y ? y : x;
}
template <class T>
inline void dec(T &x, T y) {
    x -= y;
    if (x < 0) x += mod;
}
template <class T>
inline void add(T &x, T y) {
    x += y;
    if (x >= mod) x -= mod;
}
template <typename T>
void read(T &x) {
    cin >> x;
}
template <typename T, typename... Args>
void read(T &first, Args &...args) {
    read(first);
    read(args...);
}
template <class T>
int ctz(T a) {
    return sizeof(T) > 2 ? __builtin_ctzll(a) : __builtin_ctz(a);
}
template <class T>
inline T gcd(T _a, T _b) {
    T a = abs(_a), b = abs(_b);
    int shift = ctz(a | b);
    for (b >>= ctz(b), a >>= ctz(a); a; a -= b, a >>= ctz(a))
        if (a < b) swap(a, b);
    return b << shift;
}
const double PI = acos(-1.0);
constexpr int INF = 0x3f3f3f3f;
constexpr ll linf = 0x3f3f3f3f3f3f3f3f;
constexpr ull base = 2333, P_1 = 19260817, P_2 = 999998639;
constexpr int maxn =
    1e6 + 10;  // remember to calculate. if tle, check maxn first.
// 及时当勉励
int n, m;
struct Node {
    int v, w;
    Node(int v_, int w_) { v = v_, w = w_; }
};
vector<Node> g[maxn];

int father[maxn], sz[maxn];
int dis[maxn];
int dep[maxn];
vi anss;
int fa[maxn], dfn[maxn], pos[maxn], decr, timee, top[maxn], son[maxn];
void dfs(int u, int fa, int deep) {
    father[u] = fa;
    dep[u] = deep;
    sz[u] = 1;
    for (int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i].v;
        if (v == fa) continue;  //

        dis[v] = dis[u] + g[u][i].w;
        dfs(v, u, deep + 1);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) {
            son[u] = v;
        }
    }
}

int p[maxn][30];
void Init_LCA() {
    for (int j = 0; (1 << j) <= n; ++j)
        for (int i = 1; i <= n; ++i) p[i][j] = -1;
    for (int i = 1; i <= n; ++i) p[i][0] = father[i];
    for (int j = 1; (1 << j) <= n; ++j)
        for (int i = 1; i <= n; ++i)
            if (p[i][j - 1] != -1) p[i][j] = p[p[i][j - 1]][j - 1];
}
map<pii, int> mp;
int LCA(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    int i, lg;
    for (lg = 0; (1 << lg) <= dep[x]; ++lg)
        ;
    --lg;
    /// 使x往上走直到和y在同一水平线上；
    for (i = lg; i >= 0; --i)
        if (dep[x] - (1 << i) >= dep[y]) x = p[x][i];
    if (x == y) return x;
    /// 此时x，y在同一水平线上，使x，y同时以相同的速度(2^j)往上走；
    for (i = lg; i >= 0; --i)
        if (p[x][i] != -1 && p[x][i] != p[y][i]) x = p[x][i], y = p[y][i];
    return father[x];
}

namespace Seg {
int sum[maxn * 4];
#define ls (o << 1)
#define rs (o << 1 | 1)
#define mid ((l + r) >> 1)
void build(int o, int l, int r) {
    sum[o] = 0;
    if (l == r) return;
    build(ls, l, mid), build(rs, mid + 1, r);
}

int query(int o, int l, int r, int L, int R) {
    if (L <= l && R >= r) return sum[o];
    int ret = 0;
    if (L <= mid) ret += query(ls, l, mid, L, R);
    if (R > mid) ret += query(rs, mid + 1, r, L, R);
    return ret;
}
void modify(LL o, LL l, LL r, int x) {
    sum[o]++;
    if (l == r) return;
    if (x <= mid)
        modify(ls, l, mid, x);
    else
        modify(rs, mid + 1, r, x);
}
}  // namespace Seg
using namespace Seg;

vector<pii> SS[maxn];
vi Q[maxn];

void dfs2(LL u, LL f, LL tp) {
    fa[u] = f;
    dfn[u] = ++timee;
    pos[timee] = u;
    top[u] = tp;
    if (son[u]) {
        dfs2(son[u], u, tp);
    }
    for (LL i = 0; i < g[u].size(); ++i) {
        LL v = g[u][i].v;
        if (v == f || v == son[u]) continue;
        dfs2(v, u, v);
    }
}
void dfs3(LL u, LL f) {
    static int id[maxn], cnt[maxn];
    LL tmp(0);
    for (LL i = 0; i < g[u].size(); ++i) {
        LL v = g[u][i].v;
        if (v == f) continue;
        dfs3(v, u);
        id[v] = ++tmp;
    }
    for (LL i = 0; i < SS[u].size(); ++i) {
        int x(SS[u][i].first), y(SS[u][i].second);
        if (x != u) {
            decr += cnt[x];
            cnt[x]++;
        }
        if (y != u) {
            decr += cnt[y];
            cnt[y]++;
        }
        if (x != u && y != u) {
            if (id[x] > id[y]) swap(x, y);
            decr -= mp[pii(x, y)];
            mp[pii(x, y)]++;
        }
    }
}

LL upp(int x, LL len) {
    for (LL i = 20; i >= 0; --i)
        if ((len >> i) & 1) x = p[x][i];
    return x;
}
int qry(int x, int y) {
    LL ret(0);
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ret += Seg::query(1, 1, n, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    ret += Seg::query(1, 1, n, dfn[x], dfn[y]);
    return ret;
}
void change(int x) { Seg::modify(1, 1, n, dfn[x]); }

tuple<int , int , int > qy[300010];
int32_t main() {
    close;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int x, y, w;
        cin >> x >> y;
        w = 1;
        g[x].push_back(Node(y, w));
        g[y].push_back(Node(x, w));
    }
    dis[1] = 1;
    dfs(1, -1, 1);
    Init_LCA();
    dfs2(1,0,1);
    cin >> m;
    int kp = 1;
    for(int i = 1; i <= m;i++) {
        int x, y;
        cin >> x >> y;
        LL z(LCA(x, y));
        Q[dep[z]].eb(i);
        // std::cout << "z === " << z << "  " << dep[z] << "\n";
        qy[i] = make_tuple(x,y,z);
        kp++;
    }
    cerr << "fuck" << endl;
    Seg::build(1, 1, n);
    cerr << "yy" << endl;
    ll Ans = 0;
    for (LL i = n; i >= 1; --i) {
        int sz = Q[i].size();
        if (!sz) continue;
        static int cnt[maxn];
        // cout << "sjad" << endl;
        for (LL j = 0; j < Q[i].size(); ++j) {
            LL now = (Q[i][j]);
            auto [x, y , z] = qy[now];
            Ans += cnt[z];
            cnt[z]++;
            Ans += qry(x, z) + qry(y, z);
        }
        for (LL j = 0; j < Q[i].size(); ++j) {
            LL now(Q[i][j]);
            auto [x, y , z] = qy[now];
            change(z);
        }
    }
    // cerr << "now " << endl;
    Seg::build(1, 1, n);
    decr = 0;
    // cout << "fuckk" << endl;
    for (LL i = n; i >= 1; --i) {
        for (LL j = 0; j < Q[i].size(); ++j) {
            int now = Q[i][j];
            auto [x, y , z] = qy[now];
            int ttt = (qry(x, z) + qry(y, z));
            decr += ttt;
        }
        for (LL j = 0; j < Q[i].size(); ++j) {
            LL now = Q[i][j];
            auto [x, y , z] = qy[now];
            if (x != z) {
                LL len = dep[x] - dep[z];
                len --;
                x = upp(x, len);
                change(x);
                anss.eb(x);
            }
            if (y != z) {
                int len = dep[y] - dep[z];
                len--;
                y = upp(y, len);
                change(y);
            }
            SS[z].eb(x, y);
        }
    }
    dfs3(1, 0);
    int fk =  Ans - decr;
    cout <<fk  << endl;
    // while (m--) {
    //     int x, y;
    //     scanf("%d%d", &x, &y);
    //     printf("%d\n", dis[x] + dis[y] - 2 * dis[LCA(x, y)]);
    // }
}
/*
Though leaves are many , the root is one.
Through all the lying days of my youth
I swayed my leaves and flowers in the sun.
Now I may wither into the truth.
                    - William Butler Yeats
*/