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 <bits/stdc++.h>
#define meow(args...) fprintf(stderr, args)
template<class T1, class T2> inline bool cmin(T1 &a, const T2 &b) {return b<a?(a=b, true):false;}
template<class T1, class T2> inline bool cmax(T1 &a, const T2 &b) {return a<b?(a=b, true):false;}
template<class Type> Type read() {
	Type a;
	bool b;
	unsigned char c;
	while(c=getchar()-48, (c>9)&(c!=253));
	for(a=(b=c==253)?0:c; (c=getchar()-48)<=9; a=a*10+c);
	return b?-a:a;
}
auto rd=read<int>;

const int N=2000;
int n, m, src, arg, par[N][N], mark[N][N], ans;
std::vector<int> tr[N];
std::vector<std::pair<int, int>> list;
void predfs(int u) {
	for(int v: tr[u])
		if(v!=par[src][u]) {
			par[src][v]=u;
			predfs(v);
		}
}
void dfs(int u) {
	mark[src][u]=arg;
	for(int v: tr[u])
		if(v!=par[src][u])
			if(~mark[src][v]) list.emplace_back(arg, v); else dfs(v);
}
void sol(int u, int p, int b) {
	if(mark[b][u]==u) ++ans, b=u;
	for(int v: tr[u]) if(v!=p) sol(v, u, b);
}
int main() {
	n=rd(), m=rd();
	for(int i=1; i<n; ++i) {
		int u=rd()-1, v=rd()-1;
		tr[u].push_back(v);
		tr[v].push_back(u);
	}
	for(src=0; src<n; ++src) par[src][src]=-1, predfs(src);
	for(int i=0; i<n; ++i) memset(mark[i], -1, n*sizeof(int));
	while(m--) {
		int u=rd()-1, v=rd()-1;
		list.emplace_back(u, v);
		while(!list.empty()) {
			u=list.back().first, v=list.back().second;
			list.pop_back();
			while(u!=v&&~mark[u][v]) u=mark[u][v];
			while(u!=v&&~mark[v][u]) v=mark[v][u];
			if(u==v) continue;
			src=u, dfs(arg=v);
			src=v, dfs(arg=u);
		}
	}
	for(int i=0; i<n; ++i) for(int j: tr[i]) sol(j, i, i);
	printf("%d\n", ans/2);
	return 0;
}