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;
const int maxn=3e5+5;
int n,fa[maxn][25],depth[maxn],lg[maxn],d[maxn],cnt[maxn],ct[maxn];
vector<int>e[maxn];
struct node{
    int lca,z,y;
};

void dfs(int f,int fath) //第二步:f表示当前节点，fath表示它的父亲节点
{
    depth[f]=depth[fath]+1;
    fa[f][0]=fath;
    for(int i=1;(1<<i)<=depth[f];i++)
        fa[f][i]=fa[fa[f][i-1]][i-1]; //这个转移可以说是算法的核心之一
    //意思是f的2^i祖先等于f的2^(i-1)祖先的2^(i-1)祖先
    //2^i=2^(i-1)+2^(i-1)
    for(auto i:e[f])
    {
        if(i==fath)continue;
        dfs(i,f);
    }
}
node get_node(int x,int y)//第三步,求出LCA
{
    if(depth[x]<depth[y]) //用数学语言来说就是：不妨设x的深度 >= y的深度
        swap(x,y);
    while(depth[x]>depth[y]+1) x=fa[x][lg[depth[x]-depth[y]-1]-1]; //先跳到同一深度
    if(fa[x][0]==y)return {y,x,0};
    if(depth[x]>depth[y])x=fa[x][0];
    for(int k=lg[depth[x]]-1;k>=0;k--) //不断向上跳（lg就是之前说的常数优化）
        if(fa[x][k]!=fa[y][k])  //因为我们要跳到它们LCA的下面一层，所以它们肯定不相等，如果不相等就跳过去。
            x=fa[x][k], y=fa[y][k];
    return {fa[x][0],min(x,y),max(x,y)};  //返回父节点
}
map<pair<int,int>,int>num;
pair<int,int>Que[maxn];
node Que_node[maxn];
void DFS(int now,int from)
{
    for(auto i:e[now])
    {
        if(i==from)continue;
        DFS(i,now);
        d[now]+=d[i];
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) //第一步:预先算出log_2(i)+1的值，用的时候直接调用就可以了
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);  //看不懂的可以手推一下

    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    int m;cin>>m;
    long long ans=0;
    for(int i=1;i<=m;i++)
    {
        int u,v;cin>>u>>v;
        node gget=u==v?(node){u,0,0}:get_node(u,v);
        Que_node[i]=gget;
        Que[i]={u,v};
        d[gget.lca]--;
        d[fa[gget.lca][0]]--;
        d[u]++,d[v]++;
        if(gget.z)cnt[gget.z]++;if(gget.y)cnt[gget.y]++;
        ct[gget.lca]++;
        if(gget.z && gget.y)num[{gget.z,gget.y}]++;

    }
    DFS(1,0);
    d[0]=0;
    long long  part1=0;
    for(int i=1;i<=m;i++)
    {
        int lca=Que_node[i].lca,z=Que_node[i].z,y=Que_node[i].y;
        if(!z && !y)part1+=ct[lca]-1,ans+=d[lca]-ct[lca];
        else part1+=ct[lca]-cnt[z]-cnt[y]+num[{z,y}], ans+=d[lca]-ct[lca]-(d[z]-ct[z]-cnt[z])-(d[y]-ct[y]-cnt[y]);
    }
    cout<<(part1/2+ans)<<'\n';
    return 0;
}