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 ULL unsigned long long
using namespace std;
template <typename T> void read(T &x){
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
	x *= f;
}
inline void write(int x){if (x > 9) write(x/10); putchar(x%10+'0'); }

const int N = 2048+50,E = N * N;
int n,G[N][N],ex[E],ey[E],m; 

ULL ALL;
struct data{
	ULL a[32];
	inline bool ask(int x){ return a[x>>6]>>(x&63)&1; }
	inline void ins(int x){ a[x>>6] |= 1ull<<(x&63); }
	inline void del(int x){ a[x>>6] &= ALL ^ (1ull<<(x&63)); }
	inline void And(data &w){ for (int i = 0; i < 32; ++i) a[i] &= w.a[i]; }
	inline void Or(data &w){ for (int i = 0; i < 32; ++i) a[i] |= w.a[i]; }
	inline void Xor(data &w){ for (int i = 0; i < 32; ++i) a[i] ^= w.a[i]; }
	inline void init(){ memset(a,0,sizeof(a)); }
	inline void init(data &w){ memcpy(a,w.a,sizeof(a)); }
}AL,T[N],S0[N],S1[N],tmp,tmp1,tmp2;



int lowb[1<<22],bitt[(1<<21)+1],al22;

int fa[N],dpt[N],siz[N],son[N],id[N],tl[N],tr[N],top[N],pos[N],Time;

inline void add(int x,int y){
	if (G[x][y] || x == y || !x || !y) return;
	G[x][y] = G[y][x] = 1;
//	cerr<<"ADD "<<min(x,y)<<' '<<max(y,x)<<'\n';
	++m; ex[m] = x; ey[m] = y;
	S1[x].ins(id[y]),S1[y].ins(id[x]);
	S0[x].del(id[y]),S0[y].del(id[x]);
}

int f[N][16];
inline void dfs1(int x){
	dpt[x] = dpt[fa[x]] + 1,siz[x] = 1;
	f[x][0] = fa[x];
	for (int i = 1; i < 16; ++i) f[x][i] = f[f[x][i-1]][i-1];
	for (int y = 1; y <= n; ++y) if (y != fa[x] && T[x].ask(y)){
		fa[y] = x; dfs1(y); siz[x] += siz[y];
		if (siz[y] > siz[son[x]]) son[x] = y;
	}
}
inline void dfs2(int x){
	id[x] = tl[x] = ++Time; pos[Time] = x;
	if (son[x]) top[son[x]] = top[x],dfs2(son[x]);
	for (int y = 1; y <= n; ++y) if (!top[y] && T[x].ask(y)){
		top[y] = y,dfs2(y);
	}
	tr[x] = Time;
}
inline int Jump(int x,int y){
	for (int i = 15; i >= 0; --i) if (dpt[f[y][i]] > dpt[x]) y = f[y][i];
	return y;
}
inline int LCA(int x,int y){
	while (top[x] ^ top[y]){
		if (dpt[top[x]] > dpt[top[y]]) x = fa[top[x]]; else y = fa[top[y]];
	}
	return dpt[x] <= dpt[y] ? x : y; 
}

struct Line{
	int l,r;
	bool operator < (const Line w) const{ return l < w.l; }
}g[N]; int cntg;
ULL pree[64];
inline void addl(int l,int r){ if (l > r) return; ++cntg; g[cntg].l = l; g[cntg].r = r; }
inline ULL qwq(int l,int r){ if (l > r) return 0; if (l==0) return pree[r]; return (pree[r]) ^ (pree[l-1]); }
inline void Get(data &tmp,int x,int y){
	tmp.init(),cntg = 0;
	int lca = LCA(x,y),z,l,r,ll,rr;
	if (x != lca && y != lca){
		addl(tl[x]+1,tr[x]); addl(tl[y]+1,tr[y]);
		while (top[x] ^ top[y]){
			if (dpt[top[x]] < dpt[top[y]]) swap(x,y);
			addl(id[top[x]],id[x]);
			x = fa[top[x]];
		}
		l = id[x],r = id[y]; if (l > r) swap(l,r); addl(l,r);
	}
	else{
		if (y == lca) swap(x,y);
		z = Jump(lca,y); addl(1,tl[z]-1),addl(tr[z]+1,n);
		addl(tl[y]+1,tr[y]);
		while (top[y] ^ top[z]){
			addl(id[top[y]],id[y]);
			y = fa[top[y]];
		}
		l = id[y],r = id[z]; if (l > r) swap(l,r); addl(l,r);
	}
	sort(g+1,g+cntg+1);
	int now = 1;
	for (int i = 0; i < 32 && now <= cntg; ++i){
		l = i * 64,r = i * 64 + 63;
		while (now <= cntg && g[now].r < l) ++now;
		while (now <= cntg && g[now].l <= r){
			assert(now == cntg || g[now].r < g[now+1].l);
			ll = g[now].l,rr = g[now].r;
			tmp.a[i] |= qwq(max(ll,l)-l,min(rr,r)-l);
			if (rr >= r) break;
			else ++now;
		}
	}
//	for (int i = 1; i <= cntg; ++i){
//		for (int j = g[i].l; j <= g[i].r; ++j) assert(tmp.ask(j));
//	}
}


int main(){
	int i,j,x,y,bs,bas,t,tt; ULL s; 
//	freopen("puzzle.in","r",stdin); freopen("puzzle.out","w",stdout);
	for (i = 0; i <= 63; ++i) ALL |= 1ull<<i;
	pree[0] = 1;
	for (i = 1; i <= 63; ++i) pree[i] = pree[i-1] | (1ull<<i);
	for (i = 0; i < (1<<22); ++i) lowb[i] = i & (-i);
	al22 = (1<<22)-1;
	for (i = 0; i <= (1<<21); ++i) bitt[i] = -1;
	for (i = 0; i < 22; ++i) bitt[1<<i] = i;
	read(n),read(m);
	for (i = 1; i <= n; ++i) AL.ins(i);
	for (i = 1; i <= n; ++i) S0[i].init(AL),S1[i].init();
	for (i = 1; i < n; ++i) read(x),read(y),T[x].ins(y),T[y].ins(x);
	
	dfs1(1),top[1] = 1,dfs2(1);
	
	for (i = 1; i <= m; ++i){
		read(ex[i]),read(ey[i]);
		G[ex[i]][ey[i]] = G[ey[i]][ex[i]] = 1;
		S1[ex[i]].ins(id[ey[i]]),S1[ey[i]].ins(id[ex[i]]);
		S0[ex[i]].del(id[ey[i]]),S0[ey[i]].del(id[ex[i]]);
	}
	while (m){
		x = ex[m],y = ey[m],--m;
		if (x == y) continue;
		tmp1.init(S0[x]),tmp1.And(S1[y]);
		tmp2.init(S0[y]),tmp2.And(S1[x]);
		tmp1.Or(tmp2);
		cntg = 0; Get(tmp,x,y);
		tmp.And(tmp1);
		tmp.del(id[x]),tmp.del(id[y]);
		for (bs = i = 0; i < 32; ++i,bs += 64) if (tmp.a[i]){
			s = tmp.a[i],bas = bs;
			while (s){
				t = s&al22;
				while (t) tt = pos[bitt[lowb[t]]+bas],add(x,tt),add(y,tt),t ^= lowb[t];
				s>>=22,bas+=22;
			}
		}
		continue;
	}
	int ans = 0;
	for (i = 1; i <= n; ++i)
	for (j = i+1; j <= n; ++j) if (G[i][j]) ++ans;
	cout << ans << '\n';
	return 0;
}