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;
typedef long long ll;
typedef unsigned long long u64;

#define Please return
#define AC 0
#define cin Mizuhashi
#define cout Parsee
#define endl '\n'

class Reader{
	private:
	    static const int BUF_SIZE = 1 << 22;
	    char BUF_R[BUF_SIZE], *csy1, *csy2;
	    #ifndef _NATIVE_RUNNING
		    #define GC (csy1 == csy2 && (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin), csy1 == csy2) ? EOF : *csy1 ++)
		#else
		    char cur;
		    #define GC (cur = getchar())
		#endif
	    #define IL inline
	    template <class T>
	    inline void RI(T &t) {
	    	int u = 0;
            char c = GC;
	    	for (t = 0; c < 48 || c > 57; c = GC)
                if (c == EOF) return;
                else if (c == '-') u = 1;
	    	for (;c > 47 && c < 58; c = GC) t = (t << 1) + (t << 3) + (c ^ 48);
	    	t = u ? -t : t;
		}
		template <class T>
		inline void RI(T &t, char &last) {
		    int u = 0;
            char c = GC;
	    	for (t = 0; c < 48 || c > 57; c = GC)
                if (c == EOF) return;
                else if (c == '-') u = 1;
	    	for (;c > 47 && c < 58; c = GC) t = (t << 1) + (t << 3) + (c ^ 48);
	    	t = u ? -t : t; last = c;
		}
		
    public:
        IL bool eof() {
            #ifndef _NATIVE_RUNNING
                return csy1 == csy2 && (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin), csy1 == csy2);
            #else
                return cur == EOF;
            #endif
        }
    	IL Reader& operator >> (char &c) {c = GC; return *this;}
    	IL Reader& operator >> (int &t) {RI(t); return *this;}
    	IL Reader& operator >> (ll &t) {RI(t); return *this;}
    	IL Reader& operator >> (short &t) {RI(t); return *this;}
    	IL Reader& operator >> (u64 &t) {RI(t); return *this;}
    	IL Reader& operator >> (double &t) {
    	    int tmp;
    	    char last;
            RI(tmp, last);
            t = tmp;
    	    if (last == '.') {
    	        double x = 1;
    	        for (char c = GC; c > 47 && c < 58; c = GC) t += (x /= 10) * (c ^ 48);
    	    }
    	    return *this;
    	}
    	IL Reader& operator >> (char *s) {
			char c = GC;
			for (*s = 0; c < 33; c = GC) if (c == EOF) return *this;
			for (; c > 32; c = GC) *s ++ = c;
			*s = 0; return *this;
		}
}cin;
class Writer{
	private:
	    static const int BUF_SIZE = 1 << 22;
	    char BUF_W[BUF_SIZE], *csy;
	    #define IL inline
		inline void WC(const char c) {
			if (csy - BUF_W == BUF_SIZE) fwrite(BUF_W, 1, BUF_SIZE, stdout), csy = BUF_W;
			*csy ++ = c;
		}
		template <class T>
		inline void WI(T x) {
			static int sta[32], top;
			if (x < 0) {
				WC('-');
                do sta[top ++] = - (x % 10); while (x /= 10);
			}else do sta[top ++] = x % 10; while (x /= 10);
			while (top) WC(sta[-- top] ^ 48);
		}
	
	public:
		Writer() : csy(BUF_W) {}
		~ Writer() {fwrite(BUF_W, 1, csy - BUF_W, stdout);}
		IL void flush() {fwrite(BUF_W, 1, csy - BUF_W, stdout); csy = BUF_W;}
		IL Writer& operator << (const char &c) {WC(c); return *this;}
		IL Writer& operator << (int x) {WI(x); return *this;}
		IL Writer& operator << (short x) {WI(x); return *this;}
		IL Writer& operator << (ll x) {WI(x); return *this;}
		IL Writer& operator << (u64 x) {WI(x); return *this;}
		IL Writer& operator << (const char *s) {while (*s) WC(*s ++); return *this;}
}cout;

const int MAX_N = 300000 + 5;
int n, m, cnt, tot;
struct Edge{
    int y, prev;
}e[MAX_N << 1];
int elast[MAX_N], ecnt;
int dep[MAX_N], lg[MAX_N], f[MAX_N][20];
int s[MAX_N], t[MAX_N], lca[MAX_N];
int a[MAX_N], b[MAX_N << 1], c[MAX_N];
unordered_map <int, int> g[MAX_N], h[MAX_N];
int sz[MAX_N], bs[MAX_N];
#define vp vector < pair <int, int> >
vp lazy[MAX_N];
ll sum1, sum2;

void Build(int x, int y) {
    ecnt ++;
    e[ecnt].y = y;
    e[ecnt].prev = elast[x];
    elast[x] = ecnt;
}

void dfs1(int u, int fath) {
    f[u][0] = fath;
    dep[u] = dep[fath] + 1;
    for (int i = 1; i <= lg[dep[u]]; i ++) f[u][i] = f[f[u][i - 1]][i - 1];
    for (int i = elast[u]; i; i = e[i].prev) {
        int v = e[i].y;
        if (v != fath) dfs1(v, u);
    }
}

int Lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = lg[dep[u] - dep[v]]; i >= 0; i --)
        if (dep[v] <= dep[f[u][i]]) u = f[u][i];
    if (u == v) return u;
    for (int i = lg[dep[u]]; i >= 0; i --)
        if (f[u][i] != f[v][i]) {
            u = f[u][i]; v = f[v][i];
        }
    return f[u][0];
}

int jump(int u, int lca) {
    for (int i = lg[dep[u] - dep[lca]]; i >= 0; i --)
        if (dep[lca] < dep[f[u][i]]) u = f[u][i];
    return u;
}

void dfs2(int u, int fath) {
    for (int i = elast[u]; i; i = e[i].prev) {
        int v = e[i].y;
        if (v != fath) {
            dfs2(v, u);
            sz[u] += sz[v];
        }
    }
    for (vp :: iterator it = lazy[u].begin(); it != lazy[u].end(); it ++)
        sum1 += sz[u] - sz[it -> first] - sz[it -> second] + bs[it -> first] + bs[it -> second];
}

int main() {
    cin >> n;
    for (int i = 2; i <= n; i ++) {
        lg[i] = lg[i >> 1] + 1;
        int u, v;
        cin >> u >> v;
        Build(u, v); Build(v, u);
    }
    dfs1(1, 0);
    cin >> m;
    for (int i = 1; i <= m; i ++) {
        cin >> s[i] >> t[i];
        lca[i] = Lca(s[i], t[i]);
        a[lca[i]] ++;
        sz[s[i]] ++; sz[t[i]] ++; sz[lca[i]] -= 2;
        if (s[i] != lca[i]) s[i] = jump(s[i], lca[i]);
        else s[i] = 0;
        if (t[i] != lca[i]) t[i] = jump(t[i], lca[i]);
        else t[i] = 0;
        if (t[i] < s[i]) swap(s[i], t[i]);
        lazy[lca[i]].push_back(make_pair(s[i], t[i]));
        if (s[i]) {
            if (!g[lca[i]].count(s[i])) g[lca[i]][s[i]] = ++ cnt;
            b[g[lca[i]][s[i]]] ++; bs[s[i]] ++;
        }
        if (t[i]) {
            if (!g[lca[i]].count(t[i])) g[lca[i]][t[i]] = ++ cnt;
            b[g[lca[i]][t[i]]] ++; bs[t[i]] ++;
        }
        if (s[i] && t[i]) {
            if (!h[s[i]].count(t[i])) h[s[i]][t[i]] = ++ tot;
            c[h[s[i]][t[i]]] ++;
        }
    }
    dfs2(1, 0);
    for (int i = 1; i <= m; i ++) {
        sum2 += a[lca[i]] - 1;
        if (s[i]) sum2 -= b[g[lca[i]][s[i]]] - 1;
        if (t[i]) sum2 -= b[g[lca[i]][t[i]]] - 1;
        if (s[i] && t[i]) sum2 += c[h[s[i]][t[i]]] - 1;
    }
    cout << (sum1 + sum2 / 2) << endl;
    return 0;
}