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;

#define ii pair<int,int>
#define fi first
#define se second
#define ld long double
#define vi vector<int>
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define eb emplace_back

const int mxn = 3e5+5;
const int bt = 19;

vector<int>adj[mxn];
vector<ii>query[mxn];
int h[mxn],par[bt][mxn],cnt[2][mxn];
int64_t ans;

void dfs(int u=1, int p=0){
	par[0][u]=p;
	h[u]=h[p]+1;
	for(int v:adj[u]){
		if(v!=p)dfs(v,u);
	}
	return;
}

int lca(int u, int v){
	if(h[u]<h[v])swap(u,v);
	int d = h[u]-h[v];
	for(int i=0; i<bt; i++){
		if((d>>i)&1)u=par[i][u];
	}
	if(u==v)return u;
	for(int i=bt-1; i>=0; i--){
		if(par[i][u]!=par[i][v]){
			u=par[i][u];
			v=par[i][v];
		}
	}
	return par[0][u];
}

int lift(int u, int d){
	if(d<0)return -1;
	if(d==0)return u;
	for(int i=0; i<bt; i++){
		if((d>>i)&1)u=par[i][u];
	}
	return u;
}

void solve(int cur=1){
	//solve when cur is the intersection point
	for(int v:adj[cur]){
		if(v==par[0][cur])continue;
		solve(v);
		cnt[0][cur]+=cnt[0][v];
		cnt[1][cur]+=cnt[1][v];
	}
	int sum = cnt[1][cur];
	//cerr<<cur<<"  "<<cnt[0][cur]<<" "<<cnt[1][cur]<<"\n";
	//at most intersections = sum*(sum-1)/2
	map<ii,int64_t>mp;
	for(auto qq:query[cur]){
		int u=qq.fi, v=qq.se;
		ans += (int64_t)(--sum);
		//denote pu as the point before going to LCA along the path u to v, aka path son of LCA for the path
		//same goes to pv
		//use cnt[0][x] to calc the no. of intersections of path using x to LCA, gonna cancel out 
		//once cancel, only add back the same pu,pv or pv,pu because double cancelation
		int pu=lift(u,h[u]-h[cur]-1);
		int pv=lift(v,h[v]-h[cur]-1);
		//cerr<<u<<" "<<pu<<" :: "<<v<<" "<<pv<<"\n";
		if(pu!=-1)ans -= (int64_t)(--cnt[0][pu]);
		if(pv!=-1)ans -= (int64_t)(--cnt[0][pv]);
		if(pu!=-1&&pv!=-1){
			if(pu>pv)swap(pu,pv);
			ans += (int64_t)mp[ii(pu,pv)]++;
		}
	}
	//cerr<<cur<<" "<<ans<<" "<<sum<<"\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin>>n;
	for(int i=0; i<n-1; i++){
		int u,v; cin>>u>>v;
		adj[u].eb(v);
		adj[v].eb(u);
	}
	dfs();
	for(int j=1; j<bt; j++){
		for(int i=1; i<=n; i++){
			if(par[j-1][i]){
				par[j][i]=par[j-1][par[j-1][i]];
			}
		}
	}
	int m; cin>>m;
	while(m--){
		int u,v; cin>>u>>v;
		int L=lca(u,v);
		cnt[0][u]++; cnt[0][v]++; cnt[0][L]-=2;
		cnt[1][u]++; cnt[1][v]++; cnt[1][L]--; cnt[1][par[0][L]]--;
		query[L].eb(u,v);
	}
	ans=0;
	solve();
	cout<<ans<<"\n";
	return 0;
}

/* modified from WZYYN's sol: https://codeforces.com/contest/1486/submission/108145630
 * cnt[0]:=no. of path continues to par
 * cnt[1]:=current no. of path
 */ 
