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>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
using namespace std;

// #define int long long
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
ll mod = (1000000007LL);
inline ll Mod(ll a, ll b){return (a%b);}
inline ll poww(ll a, ll b){ll res = 1;while (b > 0){if(b & 1) res = (res * a)%mod;a = (a * a)%mod;b >>= 1;}return res;}
ll gcd (ll a, ll b) { while (b) { a %= b,swap(a, b);}return a;}
void read(vector<int> &w, int n){w.resize(n);for(int i = 0; i < n; i++) cin>>w[i];}
void print(vector<int> &w){for(int i =0; i < sz(w); i++){if(i == sz(w) - 1) cout<<w[i]<<"\n";else cout<<w[i]<<" ";}}
int prodmod(vector<int> w);
int summod(vector<int> w);
///CUIDADO COM MAXN
#define N 300050

int n, m, q, k, v[N];
ll ans;
vector<int> grafo[N];
vector<pii> caras[N];
// pii w[N];
// string s;
int ini[N], fim[N], cnt, sz[N], bit[N];
struct LCA{
	vector<int> nivel, pai;
	vector< vector<int> > anc;
	const int M = 20; // LOGN

	void dfs(int x){
		ini[x] = ++cnt;
		sz[x] = 1;
	    for(int i = 0; i<grafo[x].size();i++){
	        int v = grafo[x][i];
	        if(nivel[v] == -1){
	            nivel[v] = nivel[x] + 1;
	            pai[v] = x;
	            dfs(v);
	        	sz[x] += sz[v];
	        }
	    }
	    fim[x] = cnt;
	}
	void init(int n){
		nivel.resize(n+1);
		pai.resize(n+1);
		anc.resize(n+1);
		for(int i = 0; i <= n; i++) anc[i].resize(M);

		for(int i = 1; i<= n;i++){
      		pai[i] = nivel[i] = -1;
      		for(int j = 0; j<M;j++)
        		anc[i][j] = -1;
  		}
	    pai[1] = 1;
	    nivel[1] = 0;
	    dfs(1);
	    for(int i = 1; i<=n; i++) anc[i][0] = pai[i];
	    for(int j = 1; j<M; j++)
	        for(int i = 1; i<=n; i++)
	            anc[i][j] = anc[anc[i][j-1]][j-1];
	}
	int lca(int u, int v){
	    if(nivel[v] > nivel[u]) swap(u, v);
	    for(int i = M - 1; i>=0; i--)
	        if(nivel[u] - (1<<i) >= nivel[v]) u = anc[u][i];
	    if(u == v) return u;
	    for(int i = M - 1; i>=0; i--)
	    if(anc[u][i] != -1 & anc[u][i] != anc[v][i]){
	       u = anc[u][i];
	       v = anc[v][i];
	    }
	    return anc[u][0];
	}
	int ptr = 0;
	int find_subtree(int x, int p){
		if(x == p) return 0;
		int u = x;
		for(int j = M - 1; j >= 0; j--){
			if(nivel[u] - (1<<j) > nivel[p]) u = anc[u][j];
		}
		return u;
	}
} T;

int dp[N];
void solve(int x, int p){
	map<int, int> L,ex;
	map<pii, int> LR;
	int tot = 0;
	for(auto v: grafo[x]){
		if(v == p) continue;
		solve(v, x);
		dp[x]+=dp[v];
	}
	for(auto w: caras[x]){
		int a = T.find_subtree(w.f, x);
		int b = T.find_subtree(w.s, x);
		if(a > b) swap(a, b);
		if(a > 0) dp[a] --;
		if(b > 0) dp[b] --;
		if(a > 0 and b > 0) ans += tot - L[a] - L[b] + LR[{a, b}];
		else if(b > 0) ans +=tot - L[b];
		else ans += tot;
		L[a] ++, L[b] ++, LR[{a, b}] ++;
		tot ++;
	}
	ans += 1LL*dp[x]*tot;
	// cout<<x<<" "<<dp[x]<<" cccc "<<tot<<"\n";
	for(auto v: grafo[x]){
		if(v == p) continue;
		ans -= 1LL*dp[v]*(L[v]);
	}
	// cout<<"SOLVED "<<x<<" = "<<ans<<"\n";
}
int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n;
	for(int i = 1, a, b; i < n; i++){
		cin>>a>>b;

		grafo[a].pb(b);
		grafo[b].pb(a);
	}
	T.init(n);
	cin>>q;
	for(int i = 1; i <= q; i++){
		int a, b, c;
		cin>>a>>b;
		c = T.lca(a, b);
		caras[c].pb({a, b});
		dp[a] ++, dp[b] ++, dp[c] -= 2;
	}
	solve(1,1);
	cout<<ans<<"\n";
}
/*
    CUIDADO COM MAXN, MOD, OVERFLOW 
    >Colocar (>DEFINE INT LONG LONG<) no inicio do template
    >mod = (1e9 + 7), por padrao (NAO ESQUECER DE ALTERAR)
    >NAO ESQUECER DEFINE INT LONG LONG
    > N = 1 ? 
*/
int summod(vector<int> w){int curr=0;for(int i=0;i<sz(w); i++){curr = (curr+w[i])%mod;if(curr<0)curr+=mod;}return curr;}
int prodmod(vector<int> w){int curr = 1;
for(int i = 0; i < sz(w); i++){if(w[i] >= mod) w[i] %= mod;curr = (curr * w[i]) % mod;if(curr < 0) curr += mod;}return curr;}