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.
/**
 *  created: 18/02/2021, 17:28:50
**/

#include <bits/stdc++.h>

using namespace std;

const int max_n = 300333, inf = 1000111222;
const int max_lev = 19;

int n, m, used[max_n], sz[max_n], p[max_lev][max_n], tin[max_n], tout[max_n], curt, val[max_n];
vector<int> g[max_n];
long long ans;

void calc_sz(int v, int p) {
    sz[v] = 1;
    for (int to : g[v]) {
        if (to == p || used[to]) {
            continue;
        }
        calc_sz(to, v);
        sz[v] += sz[to];
    }
}

int get_root(int v) {
    int tot = sz[v], p = -1;
    while (true) {
        int nxt = -1;
        for (int to : g[v]) {
            if (to == p || used[to]) {
                continue;
            }
            if (2 * sz[to] > tot) {
                nxt = to;
                break;
            }
        }
        if (nxt == -1) {
            return v;
        }
        p = v;
        v = nxt;
    }
}

void calc_p(int v) {
    for (int lev = 1; lev < max_lev; ++lev) {
        p[lev][v] = p[lev - 1][p[lev - 1][v]];
    }
}

void dfs(int v) {
    val[v] = 0;
    tin[v] = ++curt;
    for (int to : g[v]) {
        if (to == p[0][v] || used[to]) {
            continue;
        }
        p[0][to] = v;
        calc_p(to);
        dfs(to);
    }
    tout[v] = curt;
}

bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v) {
    if (is_ancestor(u, v)) {
        return u;
    }
    for (int i = max_lev - 1; i >= 0; --i) {
        if (!is_ancestor(p[i][u], v)) {
            u = p[i][u];
        }
    }
    return p[0][u];
}

int get_v_before_lca(int v, int lc) {
    if (v == lc) {
        return -1;
    }
    for (int i = max_lev - 1; i >= 0; --i) {
        if (!is_ancestor(p[i][v], lc)) {
            v = p[i][v];
        }
    }
    return v;
}

void push_vals(int v) {
    for (int to : g[v]) {
        if (to == p[0][v] || used[to]) {
            continue;
        }
        val[to] += val[v];
        push_vals(to);
    }
}

int cnt[3 * max_n];

void proc(vector<pair<int, int>> &v) {
    for (const auto &p : v) {
        cnt[p.first] = 0;
        cnt[p.second] = 0;
    }
    for (const auto &p : v) {
        ++cnt[p.first];
        ++cnt[p.second];
    }
    sort(v.begin(), v.end());
    long long tot = 0;
    for (int i = 0; i < v.size(); ) {
        int pos = i;
        while (i < v.size() && v[i] == v[pos]) {
            ++i;
        }
        for (int j = pos; j < i; ++j) {
            int add = v.size();
            add -= cnt[v[j].first];
            add -= cnt[v[j].second];
            add += (i - pos);
            tot += add;
        }
    }
    assert(tot % 2 == 0);
    tot /= 2;
    ans += tot;
}

void solve(int root, const vector<pair<int, int>> &paths) {
    calc_sz(root, root);
    //cout << root << " -> ";
    root = get_root(root);
    //cout << "#" << root << endl;
    p[0][root] = root;
    calc_p(root);
    curt = -1;
    dfs(root);
    int num = n;
    vector<pair<int, int>> v;
    vector<int> lcs;
    for (auto p : paths) {
        int lc = lca(p.first, p.second);
        int v1 = get_v_before_lca(p.first, lc);
        int v2 = get_v_before_lca(p.second, lc);
        lcs.push_back(lc);
        //cout << p.first << " " << p.second << ", lca = " << lc << endl;
        if (lc == root) {
            if (v1 == -1) {
                v1 = ++num;
            }
            if (v2 == -1) {
                v2 = ++num;
            }
            if (v1 > v2) {
                swap(v1, v2);
            }
            v.push_back({v1, v2});
        } else {
            ++val[lc];
            if (v1 != -1) {
                --val[v1];
            }
            if (v2 != -1) {
                --val[v2];
            }
        }
    }
    proc(v);
    push_vals(root);
    vector<pair<int, pair<int, int>>> npaths;
    for (int i = 0; i < lcs.size(); ++i) {
        int lc = lcs[i], v1 = paths[i].first, v2 = paths[i].second;
        if (lc == root) {
            if (v1 != root) {
                ans += val[v1];
            }
            if (v2 != root) {
                ans += val[v2];
            }
        } else {
            int nxt = get_v_before_lca(lc, root);
            //cout <<"i = " << i << ", " << nxt << endl;
            npaths.push_back({nxt, paths[i]});
        }
    }
    used[root] = 1;
    sort(npaths.begin(), npaths.end());
    for (int i = 0; i < npaths.size(); ) {
        int pos = i;
        while (i < npaths.size() && npaths[pos].first == npaths[i].first) {
            ++i;
        }
        vector<pair<int, int>> ps(i - pos);
        for (int j = pos; j < i; ++j) {
            ps[j - pos] = npaths[j].second;
        }
        solve(npaths[pos].first, ps);
    }
}

const bool debug = 0;

const int seed = chrono::steady_clock::now().time_since_epoch().count();
mt19937 generator(seed);

int rnd() {
    return generator() >> 1;
}

int rnd(int r) {
    return rnd() % r;
}

int rnd(int l, int r) {
    return l + rnd(r - l + 1);
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    if (debug) {
        n = 300000;
    } else {
        scanf("%d", &n);
    }
    for (int i = 1; i < n; ++i) {
        int u, v;
        if (debug) {
            //u = i - 1;
            u = rnd(i);
            v = i;
        } else {
            scanf("%d%d", &u, &v);
            --u;
            --v;
        }
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if (debug) {
        m = 300000;
    } else {
        scanf("%d", &m);
    }
    vector<pair<int, int>> paths(m);
    for (auto &p : paths) {
        if (debug) {
            p.first = rnd(n);
            p.second = rnd(n);
        } else {
            scanf("%d%d", &p.first, &p.second);
            --p.first;
            --p.second;
        }
    }
    solve(0, paths);
    printf("%lld\n", ans);
    return 0;
}
