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<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<random>
#include<ctime>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<unordered_map>
#include<map>
#include<bitset>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=6e5+5,M=1e3+5;
const ll INF=1e18+5;
inline ll read()
{
	ll sum=0,fh=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')fh=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		sum=sum*10+c-'0';
		c=getchar();
	}
	return sum*fh;
}
inline int read2()
{
	char c=getchar();
	while(c!='a'&&c!='b'&&c!='c'&&c!='?')c=getchar();
	return c=='?'?0:c-'a'+1;
}
inline int read3()
{
	char c=getchar();
	while(c<'a'||c>'z')
	{
		c=getchar();
	}
	return c-'a';
}
inline void write(ll x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}


/*namespace INPUT_SPACE{
    const int BS=(1<<24)+5;char Buffer[BS],*HD,*TL;
    char gc() { if(HD==TL) TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);return (HD==TL)?EOF:*HD++; }
    inline ull read()
    {
        ull x,ch;while(((ch=gc())<'0'||ch>'9'));
        x=ch^'0';
        while((ch=gc())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^'0');
        return x;
    }
}using INPUT_SPACE::read;
char sws[30000011],tt[21];int ssl,ttl;
inline int write(int x)
{
    if(!x) sws[++ssl]='0';for(ttl=0;x;x/=10) tt[++ttl]=char(x%10+'0');
    for(;ttl;ttl--) sws[++ssl]=tt[ttl];return sws[++ssl]='\n';
}*/

inline int gcd(int x,int y)
{
	return y==0?x:gcd(y,x%y);
}
inline ll ab(ll x)
{
	return x<0?-x:x;
}
inline ll fpow(ll qwe,ll asd,ll zxc)
{
	if(asd<0)return 0;
	ll a=qwe,b=1,c=asd;
	while(c)
	{
		if(c&1)b=b*a%zxc;
		a=a*a%zxc;
		c>>=1;
	}
	return b;
}

int n,m;
struct miaow2
{
	int son[2];
	int fa,qfa;
	int fz;
	int sz,sum;
}t[N];
#define ls(x) t[x].son[0]
#define rs(x) t[x].son[1]
#define son(x,k) t[x].son[k]
#define fa(x) t[x].fa
#define qfa(x) t[x].qfa
#define fz(x) t[x].fz
#define sz(x) t[x].sz
#define sum(x) t[x].sum
inline int fx(int x)
{
	if(!fa(x))return -1;
	return rs(fa(x))==x;
}
inline void upd(int x)
{
	sum(x)=sz(x)+(ls(x)?sum(ls(x)):0)+(rs(x)?sum(rs(x)):0);
}
inline void pd(int x)
{
	if(!fz(x))return;
	swap(ls(x),rs(x));
	fz(x)=0;
	if(ls(x))fz(ls(x))^=1;
	if(rs(x))fz(rs(x))^=1;
}
inline void rot(int x)
{
	if(!fa(x))return;
	int y=fa(x),k=fx(x);
	if(fa(y))
	{
		fa(x)=fa(y);
		son(fa(y),fx(y))=x;
	}
	else swap(qfa(x),qfa(y)),fa(x)=0;
	fa(y)=x;
	if(son(x,k^1))fa(son(x,k^1))=y;
	son(y,k)=son(x,k^1);
	son(x,k^1)=y;
	upd(y);
	upd(x);
}
inline void pd2(int x)
{
	if(fa(x))pd2(fa(x));
	pd(x);
}
inline void splay(int x)
{
	pd2(x);
	if(!fa(x))return;
	int y=fa(x);
	while(y)
	{
		if(!fa(y))
		{
			rot(x);
			return;
		}
		int z=fa(y);
		if(fx(x)==fx(y))rot(y);
		else rot(x);
		rot(x);
		y=fa(x);
	}
}
inline void access(int x)
{
	splay(x);
	if(rs(x))
	{
		qfa(rs(x))=x;
		fa(rs(x))=0;
		rs(x)=0;
		upd(x);
	}
	int y=qfa(x);
	while(y)
	{
		splay(y);
		//cout<<y<<"."<<fz(y)<<endl;
		if(rs(y))
		{
			qfa(rs(y))=y;
			fa(rs(y))=0;
			rs(y)=0;
		}
		rs(y)=x;
		fa(x)=y;
		qfa(x)=0;
		x=y;
		y=qfa(x);
	}
}

inline void sc()
{
	for(int i=1;i<=n;++i)
	{
		cout<<i<<" ls:"<<ls(i)<<" rs:"<<rs(i)<<" fa:"<<fa(i)<<" qfa:"<<qfa(i)<<" sz:"<<sz(i)<<" sum:"<<sum(i)<<" fz:"<<fz(i)<<endl;
	}
	cout<<endl;
}

inline int hg(int x)
{
	access(x);
	//sc();
	splay(x);
	fz(x)=1;
}
inline int lctcx(int l,int r)
{
	//cout<<"cx:"<<l<<" "<<r<<endl;
	//sc();
	hg(l);
	//sc();
	access(r);
	splay(r);
	//cout<<"cx:"<<ls(r)<<" "<<rs(r)<<" "<<ls(rs(r))<<" "<<rs(rs(r))<<endl;
	//sc();
	return sum(r);
}
inline void lctxg(int x,int y)
{
	hg(x);
	sz(x)+=y;
	upd(x);
}

#define pi pair<ll,ll>
struct miaow
{
	int f,t,l;
	ll c;
	miaow(int f=0,int t=0,ll c=0,int l=0):f(f),t(t),c(c),l(l){}
}imap[N*2+5];
int str[N*2+5]={0},cou=2;
inline void jb(int f,int t,ll c=0)
{
	//cout<<f<<" "<<t<<" "<<c<<endl;
	imap[cou]=miaow(f,t,c,str[f]);str[f]=cou++;
	imap[cou]=miaow(t,f,c,str[t]);str[t]=cou++;
}
//ll a[N];
int dfn[N],dfnl[N],dfnr[N],dfncou=0,dep[N];
pi sx[N];
inline void dfs(int o,int fa,int d)
{
	sx[o]=pi(-d,o);
	dep[o]=d;
	dfn[++dfncou]=o;
	dfnl[o]=dfncou;
	for(int i=str[o];i;i=imap[i].l)
	{
		int tt=imap[i].t;
		if(tt==fa)continue;
		qfa(tt)=o;
		dfs(tt,o,d+1);
		dfn[++dfncou]=o;
	}
	dfnr[o]=dfncou;
	return;
}
struct meow
{
	int imi,l,r;
	meow(int imii=0,int ll=0,int rr=0)
	{
		imi=imii,l=ll,r=rr;
	}
};
inline meow meg(meow& qwe,meow& asd)
{
	if(qwe.imi<asd.imi)return qwe;
	if(qwe.imi>asd.imi)return asd;
	return meow(qwe.imi,min(qwe.l,asd.l),max(qwe.r,asd.r));
}
struct nya
{
	int l,r;
	meow imx;
}tt[N*4+5];
#define l(x) tt[x].l
#define r(x) tt[x].r
#define imx(x) tt[x].imx
#define lss(x) (x*2)
#define rss(x) (x*2+1)
inline void tcsh(int l,int r,int o)
{
	l(o)=l,r(o)=r;
	if(l==r)
	{
		imx(o)=meow(dep[dfn[l]],l,r);
		return;
	}
	int mid=(l+r)>>1;
	tcsh(l,mid,lss(o)),tcsh(mid+1,r,rss(o));
	imx(o)=meg(imx(lss(o)),imx(rss(o)));
}
inline meow cx(int l,int r,int o)
{
	//cout<<l<<" "<<r<<" "<<o<<endl;
	if(l<=l(o)&&r>=r(o))return imx(o);
	meow qwe(1e9,0,0),asd(1e9,0,0);
	int mid=(l(o)+r(o))>>1;
	if(l<=mid)qwe=cx(l,min(mid,r),lss(o));
	if(r>mid)asd=cx(max(mid+1,l),r,rss(o));
	return meg(qwe,asd);
}
/*inline void xg(int l,int r,int o,int x)
{
	if(l>r)return;
	if(l<=l(o)&&r>=r(o))
	{
		bj(o)+=x;
		imx(o)+=x;
		return;
	}
	int mid=(l(o)+r(o))>>1;
	if(l<=mid)xg(l,min(mid,r),ls(o),x);
	if(r>mid)xg(max(l,mid+1),r,rs(o),x);
	if(imx(ls(o))>imx(rs(o)))imx(o)=imx(ls(o))+bj(o),sum(o)=sum(ls(o));
	else if(imx(ls(o))<imx(rs(o)))imx(o)=imx(rs(o))+bj(o),sum(o)=sum(rs(o));
	else imx(o)=imx(ls(o))+bj(o),sum(o)=sum(ls(o))+sum(rs(o));
}*/
/*inline void xg(int k,int o,int x)
{
	//if(l>r)return;
	if(l(o)==r(o))
	{
		mat(o,0,0)=0;
		mat(o,0,1)=x;
		mat(o,1,0)=-x;
		mat(o,1,1)=0;
		return;
		return;
	}
	int mid=(l(o)+r(o))>>1;
	if(k<=mid)xg(k,ls(o),x);
	else xg(k,rs(o),x);
	upd(o);
}*/
/*inline int cx(int k,int o)
{
	if(l(o)==r(o))return imx(o);
	int x=imx(o),mid=(l(o)+r(o))>>1;
	if(k<=mid)return min(x,cx(k,ls(o)));
	else return min(x,cx(k,rs(o)));
}*/

struct meow2
{
	int l,r,lca,lcal,lcar;
	meow2(int ll=0,int rr=0,int lca=0,int lcal=0,int lcar=0):lca(lca),lcal(lcal),lcar(lcar)
	{
		l=ll,r=rr;
	}
};
vector<meow2> dcz[N];
int djs[N];
map<pi,int> djs2;
ll ans;
inline void csh()
{
	n=read();//,m=read();
	//cout<<"?"<<endl;
	for(int i=1;i<n;++i)
	{
		int f=read(),t=read();
		jb(f,t);
	}
	//cout<<"?"<<endl;
	dfs(1,0,1);
	//cout<<"?"<<endl;
	sort(sx+1,sx+n+1);
	//cout<<"?"<<endl;
	tcsh(1,dfncou,1);
	//cout<<"?"<<endl;
	//for(int i=1;i<=dfncou;++i)cout<<dfn[i]<<" ";cout<<endl;
	//for(int i=1;i<=n;++i)cout<<i<<" "<<dfnl[i]<<" "<<dfnr[i]<<endl;
	m=read();
	for(int i=1;i<=m;++i)
	{
		//cout<<"?"<<i<<endl;
		int l=read(),r=read();
		if(l==r)
		{
			//cout<<"!1"<<endl;
			dcz[l].push_back(meow2(l,r,l));
			//cout<<l<<" "<<r<<" "<<l<<" "<<"0 0"<<endl;
			continue;
		}
		if(dfnl[l]>dfnl[r])swap(l,r);
		if(dfnl[l]<dfnl[r]&&dfnr[l]>dfnr[r])
		{
			//cout<<"!2"<<endl;
			meow qwe=cx(dfnr[r],dfnr[l],1);
			dcz[l].push_back(meow2(l,r,l,0,dfn[qwe.l-1]));
			//cout<<l<<" "<<r<<" "<<l<<" "<<"0 "<<dfn[qwe.l-1]<<endl;
		}
		else
		{
			//cout<<"!3"<<" "<<dfnr[l]<<" "<<dfnl[r]<<endl;
			meow qwe=cx(dfnr[l],dfnl[r],1);
			//cout<<"!3"<<" "<<dfnr[l]<<" "<<dfnl[r]<<endl;
			//cout<<qwe.l<<" "<<qwe.r<<" "<<qwe.imi<<endl;
			dcz[dfn[qwe.l]].push_back(meow2(l,r,dfn[qwe.l],dfn[qwe.l-1],dfn[qwe.r+1]));
			//cout<<l<<" "<<r<<" "<<dfn[qwe.l]<<" "<<dfn[qwe.l-1]<<" "<<dfn[qwe.r+1]<<endl;
		}
	}
}
inline void solve()
{
	for(int i=1;i<=n;++i)
	{
		int o=sx[i].second;
		//cout<<"!"<<o<<endl;
		int js=0;
		for(int j=0;j<dcz[o].size();++j)
		{
			int l=dcz[o][j].l,r=dcz[o][j].r,lcal=dcz[o][j].lcal,lcar=dcz[o][j].lcar;
			//cout<<l<<" "<<r<<" "<<lcal<<" "<<lcar<<endl;
			if(l==r)
			{
				ans+=js;
				js+=1;
			}
			else if(l==o)
			{
				ans+=js-djs[lcar];
				ans+=lctcx(l,r);
				js+=1;
				djs[lcar]+=1;
			}
			else
			{
				//cout<<"?1 "<<ans<<endl;
				ans+=js-djs[lcal]-djs[lcar]+djs2[pi(lcal,lcar)];
				//cout<<"?2 "<<ans<<endl;
				ans+=lctcx(l,r);
				//cout<<"?3 "<<ans<<endl;
				js+=1;
				djs[lcal]+=1,djs[lcar]+=1;
				djs2[pi(lcal,lcar)]+=1;
			}
		}
		for(int j=0;j<dcz[o].size();++j)
		{
			int l=dcz[o][j].l,r=dcz[o][j].r,lcal=dcz[o][j].lcal,lcar=dcz[o][j].lcar;
			if(l==r)
			{
				lctxg(l,1);
			}
			else if(l==o)
			{
				lctxg(l,1);
				lctxg(lcar,-1);
			}
			else
			{
				lctxg(o,1);
				lctxg(lcal,-1);
				lctxg(lcar,-1);
			}
		}
	}
}
int main()
{
	//freopen("qwq.txt","r",stdin);
	//freopen("qaq.txt","w",stdout);
	csh();
	solve();
	cout<<ans<<endl;
	return 0;
}
