Problem: You are given a tree T with N vertices and an undirected graph G with N vertices and M edges. The vertices of each graph are numbered 1 to N. The i-th of the N-1 edges in T connects Vertex a_i and Vertex b_i, and the j-th of the M edges in G connects Vertex c_j and Vertex d_j.

Consider adding edges to G by repeatedly performing the following operation:

* Choose three integers a, b and c such that G has an edge connecting Vertex a and b and an edge connecting Vertex b and c but not an edge connecting Vertex a and c. If there is a simple path in T that contains all three of Vertex a, b and c in some order, add an edge in G connecting Vertex a and c.



Print the number of edges in G when no more edge can be added. It can be shown that this number does not depend on the choices made in the operation.

Constraints

* 2 \leq N \leq 2000
* 1 \leq M \leq 2000
* 1 \leq a_i, b_i \leq N
* a_i \neq b_i
* 1 \leq c_j, d_j \leq N
* c_j \neq d_j
* G does not contain multiple edges.
* T is a tree.

Input

Input is given from Standard Input in the following format:


N M
a_1 b_1
:
a_{N-1} b_{N-1}
c_1 d_1
:
c_M d_M


Output

Print the final number of edges in G.

Examples

Input

5 3
1 2
1 3
3 4
1 5
5 4
2 5
1 5


Output

6


Input

7 5
1 5
1 4
1 7
1 2
2 6
6 3
2 5
1 3
1 6
4 6
4 7


Output

11


Input

13 11
6 13
1 2
5 1
8 4
9 7
12 2
10 11
1 9
13 7
13 11
8 10
3 8
4 13
8 12
4 7
2 3
5 11
1 4
2 11
8 10
3 5
6 9
4 10


Output

27

Solution (in CPP):

Solution:
#include<cstdio>
#define M 4004
#define N 2002
int A[N],B[M],C[M],a[N],b[M],c[M],d[N],e[N],f[N][N],g[N][N],h[N],m,n,t;bool G[N][N];
inline int _e(int u,int v){return h[u]+h[v]-(h[f[u][v]]<<1);}
void _d(int u,int v){for(int i=A[u];i;i=B[i])if(_e(v,u)+_e(u,C[i])==_e(v,C[i]))_d(C[i],v),t++;}
void _c(int u,int v)
{
    if(g[v][u])B[++t]=A[v],C[A[v]=t]=u;
    else for(int i=a[u];i;i=b[i])if(_e(v,c[i])==_e(v,u)+1)_c(c[i],v);
}
void _b(int u,int v,int w)
{
    if(g[v][u])!G[g[v][u]][w]?G[g[v][u]][w]=G[w][g[v][u]]=1,_b(g[v][u],w,g[v][u]),_b(w,g[v][u],w),0:0;
    else
    {
        g[v][u]=w;
        for(int i=a[u];i;i=b[i])if(_e(v,c[i])==_e(v,u)+1)_b(c[i],v,w);
    }
}
void _a(int u){for(int i=a[e[d[u]=++t]=f[u][u]=u],j,k;i;i=b[i])if(!d[c[i]])for(h[c[i]]=h[u]+1,_a(c[i]),j=d[u];j<d[c[i]];j++)for(k=d[c[i]];k<=t;k++)f[e[j]][e[k]]=f[e[k]][e[j]]=u;}
int i,u,v;
int main()
{
    scanf("%d%d",&n,&m),G[n][n]=1;
    for(i=1;i<n;i++)scanf("%d%d",&u,&v),b[++t]=a[u],c[a[u]=t]=v,b[++t]=a[v],c[a[v]=t]=u,G[i][i]=1;
    for(t=0,_a(i=1);i<=m;i++)scanf("%d%d",&u,&v),!G[u][v]?G[u][v]=G[v][u]=1,_b(u,v,u),_b(v,u,v),0:0;
    for(i=1,t=0;i<=n;i++)g[i][i]=0,_c(i,i);
    for(i=1,t=0;i<=n;i++)_d(i,i);
    return 0&printf("%d\n",t>>1);
}