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 int long long
#define reg register
#define x1 x11
#define x2 x22
#define y1 y11
#define y2 y22
#define z1 z11
#define z2 z22
const int mod=998244353;
const int INF=2e18;
const int maxn=600000+5;
const double Pi=acos(-1.0);
double Exp=1e-6;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9')
	{
	    if(ch=='-')
	        f=-1;
	    ch=getchar();
	}
	while(ch>='0' && ch<='9')
	{
	    x=x*10+ch-'0';
	    ch=getchar();
	}
	return x*f;
}
int n,m;
struct node
{
	int x,y;
	int lca;
	int son[3];
}p[maxn],s[maxn];
int tot=0;
int ans=0;
struct vode
{
	int to;
	int nxt;
}edge[maxn];
int wugui=0;
int head1[maxn];
void add(int x,int y)
{
	wugui++;
	edge[wugui].to=y;
	edge[wugui].nxt=head1[x];
	head1[x]=wugui;
}
int cnt[maxn];
int tot1[maxn];
int fa[maxn][21];
int dep[maxn];
int lg[maxn];
void dfs(int x,int root)
{
	fa[x][0]=root;
	dep[x]=dep[root]+1;
	for(int i=1;i<=19;i++)
	fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=head1[x];i;i=edge[i].nxt)
	{
		int t=edge[i].to;
		if(t==root)
		continue;
		dfs(t,x);
	}
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y])
	{
		swap(x,y);
	}
	while(dep[x]>dep[y])
	x=fa[x][lg[dep[x]-dep[y]]];
	if(x==y)
	return x;
	for(int i=lg[dep[x]];i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
int love=0;
vector<int> v[maxn];
bool cmp1(node a,node b)
{
	if(a.son[1]!=b.son[1])
	return a.son[1]<b.son[1];
	return a.son[2]<b.son[2];
}
int cnt1[maxn];
int dp[maxn];
void Work(int x,int root)
{
	for(int i=head1[x];i;i=edge[i].nxt)
	{
		int t=edge[i].to;
		if(t==root)
		continue;
		Work(t,x);
		cnt1[x]=cnt1[x]+cnt1[t];
	}
}
signed main()
{	
	n=read();
	for(int i=1;i<=n;i++)
	{
		lg[i]=log2(i);
	}
	for(int i=1;i<=n-1;i++)
	{
		int x=read(),y=read();
		add(x,y);
		add(y,x);
	}
	m=read();
	for(int i=1;i<=m;i++)
	{
		p[i].x=read(),p[i].y=read();
	}
	dfs(1,0);
	for(int i=1;i<=m;i++)
	{
		p[i].lca=LCA(p[i].x,p[i].y);
		int x=p[i].x,y=p[i].y;
		int lca=p[i].lca;
		cnt[lca]++;
		int cnt1=0;
		if(x==lca && y==lca)
		{
			p[i].son[1]=--love;
			p[i].son[2]=--love;
			v[lca].push_back(i);
			continue;
		}
		if(x!=lca)
		{
			int nowx=x;
			for(int j=19;j>=0;j--)
			{
				if(fa[nowx][j] && dep[fa[nowx][j]]>dep[lca])
				nowx=fa[nowx][j];
			}
			cnt1++;
			p[i].son[cnt1]=nowx;
		}
		if(y!=lca)
		{
			int nowy=y;
			for(int j=19;j>=0;j--)
			{
				if(fa[nowy][j] && dep[fa[nowy][j]]>dep[lca])
				nowy=fa[nowy][j];
			}
			cnt1++;
			p[i].son[cnt1]=nowy;
		}
		if(p[i].son[2]==0)
		{
			p[i].son[2]=--love;
		}	
		else
		{
			if(p[i].son[2]<p[i].son[1])
			swap(p[i].son[1],p[i].son[2]);
		}
		v[lca].push_back(i);
		if(p[i].son[1]>0)
		{
			tot1[p[i].son[1]]++;
		}
		if(p[i].son[2]>0)
		{
			tot1[p[i].son[2]]++;
		}
	}
	//for(int i=1;i<=m;i++)
	//{
	//	cout<<p[i].x<<" "<<p[i].y<<" "<<p[i].lca<<" "<<p[i].son[1]<<" "<<p[i].son[2]<<endl;
	//}
	// flag=1
	for(int i=1;i<=n;i++)
	{
		//cout<<i<<" "<<cnt[i]<<endl;
		int wns=0;
		wns=cnt[i]*(cnt[i]-1)/2;
		//cout<<"ans="<<ans<<endl;
		tot=0;
		for(int j=0;j<(int)v[i].size();j++)
		{
			int x=v[i][j];
			s[++tot]=p[x];
		}
		for(int j=head1[i];j;j=edge[j].nxt)
		{
			int t=edge[j].to;
			if(t==fa[i][0])
			continue;
			wns=wns-(tot1[t]-1)*tot1[t]/2;
		}
		sort(s+1,s+1+tot,cmp1);
		int now=1;
		for(int i=2;i<=tot;i++)
		{
			if((s[i].son[1]==s[i-1].son[1] && s[i].son[2]==s[i-1].son[2]))
			now++;
			else
			{
				wns=wns+now*(now-1)/2;
				now=1;
			}
		}
		wns=wns+now*(now-1)/2;
		//cout<<"wns="<<wns<<endl;
		ans=ans+wns;
		/*
		int res=1;
		int wns=1;
		for(int j=2;j<=tot;j++)
		{
			if(s[i].son[1]!=s[i-1].son[1])
			{
				ans=ans-wns*(wns-1)/2;
				wns=1;
			}
			else
			wns++;
			if(s[i].son[1]!=s[i-1].son[1] || s[i].son[2]!=s[i-1].son[2])
			{
				ans=ans+res*(res-1)/2;
				res=1;
			}
			else
			res++;
		}
		ans=ans+res*(res-1)/2;
		ans=ans-wns*(wns-1)/2;
		sort(s+1,s+1+tot,cmp2);
		wns=1;
		for(int j=2;j<=tot;j++)
		{
			if(s[i].son[2]!=s[i-1].son[2])
			{
				ans=ans-wns*(wns-1)/2;
				wns=1;
			}
			else
			wns++;
		}
		ans=ans-wns*(wns-1)/2;*/
	}
	for(int i=1;i<=m;i++)
	{
		cnt1[p[i].x]++;
		cnt1[p[i].y]++;
		cnt1[p[i].lca]-=2;
	}
	Work(1,0);
	for(int i=1;i<=n;i++)
	{
		ans=ans+cnt1[i]*cnt[i];
		for(int j=head1[i];j;j=edge[j].nxt)
		{
			int t=edge[j].to;
			if(t==fa[i][0])
			continue;
			ans=ans-tot1[t]*(cnt1[t]-tot1[t]);
		}
	}	
	printf("%lld\n",ans);
	return 0;
}	
/*
bbbbbaababbbabaabababa
*/