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;
namespace Sakurajima_Mai{
    #define ms(a) memset(a,0,sizeof(a))
    #define repi(i,a,b) for(int i=a,bbb=b;i<=bbb;++i)//attention reg int or reg ll ?
    #define repd(i,a,b) for(int i=a,bbb=b;i>=bbb;--i)
    #define reps(s) for(int i=head[s],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
    #define ce(i,r) i==r?'\n':' '
    #define pb push_back 
    #define all(x) x.begin(),x.end()
    #define gmn(a,b) a=min(a,b)
    #define gmx(a,b) a=max(a,b)
    #define fi first
    #define se second                         
    typedef long long ll;
    typedef unsigned long long ull;
    typedef double db;
    const int infi=2e9;//infi较大，注意涉及inf相加时爆int
    const ll infl=4e18;
    inline ll ceil_div(ll a,ll b){ return (a+b-1)/b; }
    inline ll pos_mod(ll a,ll b){ return (a%b+b)%b; }
    //std::mt19937 rnd(time(0));//std::mt19937_64 rnd(time(0));
}
using namespace Sakurajima_Mai;
namespace Fast_Read{
    inline int qi(){
        int f=0,fu=1; char c=getchar();
        while(c<'0'||c>'9'){ if(c=='-')fu=-1; c=getchar(); }
        while(c>='0'&&c<='9'){ f=(f<<3)+(f<<1)+c-48; c=getchar(); }
        return f*fu;
    }
    inline ll ql(){
        ll f=0;int fu=1; char c=getchar();
        while(c<'0'||c>'9'){ if(c=='-')fu=-1; c=getchar(); }
        while(c>='0'&&c<='9'){ f=(f<<3)+(f<<1)+c-48; c=getchar(); }
        return f*fu;
    }
    inline db qd(){
        char c=getchar();int flag=1;double ans=0;
        while((!(c>='0'&&c<='9'))&&c!='-') c=getchar();
        if(c=='-') flag=-1,c=getchar();
        while(c>='0'&&c<='9') ans=ans*10+(c^48),c=getchar();
        if(c=='.'){c=getchar();for(int Bit=10;c>='0'&&c<='9';Bit=(Bit<<3)+(Bit<<1)) ans+=(double)(c^48)*1.0/Bit,c=getchar();}
        return ans*flag;
    }
}
namespace Read{
    #define si(a) scanf("%d",&a)
    #define sl(a) scanf("%lld",&a)
    #define sd(a) scanf("%lf",&a)
    #define ss(a) scanf("%s",a)
    #define rai(x,a,b) repi(i,a,b) x[i]=qi()
    #define ral(x,a,b) repi(i,a,b) x[i]=ql()
}
namespace Out{
    #define pi(x) printf("%d",x)
    #define pl(x) printf("%lld",x)
    #define ps(x) printf("%s",x)
    #define pc(x) printf("%c",x)
    #define pe() puts("")
}
namespace DeBug{
    #define MARK false
    #define DB if(MARK) 
    #define pr(x) cout<<#x<<": "<<x<<endl
    #define pra(x,a,b) cout<<#x<<": "<<endl; \
            repi(i,a,b) cout<<x[i]<<" ";     \
            puts("");   
    #define FR(a) freopen(a,"r",stdin)
    #define FO(a) freopen(a,"w",stdout)
}
using namespace Fast_Read;
using namespace Read;
using namespace Out;
using namespace DeBug;
typedef pair<int,int> P;
const int MAX_N=3e5+5;
const int MAX_E=3e5+5;
int n,m;
struct Edge{int to,nxt;}e[MAX_E<<1];
int head[MAX_N],tote;
void add_edge(int u,int v){e[++tote].to=v,e[tote].nxt=head[u];head[u]=tote;}
void init(int n)
{
    repi(i,0,n) head[i]=0;
    tote=0;
}

int p[MAX_N],dep[MAX_N],siz[MAX_N],top[MAX_N],son[MAX_N];
int idx,dfn[MAX_N],rdfn[MAX_N];
void dfs_1(int u,int fa)
{
    dep[u]=dep[fa]+1,p[u]=fa,siz[u]=1,son[u]=-1;
    reps(u)if(v!=fa){
        dfs_1(v,u),siz[u]+=siz[v];
        if(son[u]==-1||siz[son[u]]<siz[v])  son[u]=v;
    }
}
void dfs_2(int u,int tp)//不需要记录dfs序的in，out。in[x]=dfn[x],out[x]=dfn[x]+siz[x]-1 用于子树整体的询问
{
    top[u]=tp,dfn[u]=++idx,rdfn[dfn[u]]=u;
    if(son[u]==-1)  return; 
    dfs_2(son[u],tp);
    reps(u)if(v!=p[u]&&v!=son[u])   dfs_2(v,v);
}
int LCA(int x,int y)
{
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=p[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
int LCA2(int x,int y)
{
    int t;
    while(top[x]!=top[y])   t=top[y],y=p[top[y]];
    return x==y?t:son[x];
}
int cnt_lca[MAX_N],cnt_son[MAX_N];
map<P,int> inc_exc;
ll ans1=0;
void solve_1()
{
    repi(i,1,n) ans1+=1ll*cnt_lca[i]*(cnt_lca[i]-1)/2;
    repi(i,1,n) ans1-=1ll*cnt_son[i]*(cnt_son[i]-1)/2;
    for(auto x:inc_exc) ans1+=1ll*x.se*(x.se-1)/2;
}
int delta[MAX_N];
ll ans2=0;
void solve_2(int u,int fa)
{

    reps(u)if(v!=fa){
        solve_2(v,u),delta[u]+=delta[v];
        ans2-=1ll*cnt_son[v]*(delta[v]-cnt_son[v]);
    } 
    ans2+=1ll*(cnt_lca[u])*delta[u];    
}
int main()
{
    n=qi(); init(n);
    repi(i,1,n-1){
        int u=qi(),v=qi();
        add_edge(u,v),add_edge(v,u);
    }
    idx=dep[0]=0; 
    dfs_1(1,0); dfs_2(1,1);
    m=qi();
    repi(i,1,m){
        int a=qi(),b=qi(),lca=LCA(a,b); 
        cnt_lca[lca]++;
        delta[a]++,delta[b]++,delta[lca]-=2;
        if(lca==a) a=-1;
        else a=LCA2(lca,a),cnt_son[a]++;
        if(lca==b) b=-1;
        else b=LCA2(lca,b),cnt_son[b]++;
        if(a>b) swap(a,b); 
        if(a!=-1&&b!=-1) inc_exc[P(a,b)]++;
    }
    solve_1(),solve_2(1,0);
    pl(ans1+ans2),pe();
    return 0;
}

