传说中的暗之连锁被人们称为 Dark。

Dark 是人类内心的黑暗的产物，古今中外的勇者们都试图打倒它。

经过研究，你发现 Dark 呈现无向图的结构，图中有 N 个节点和两类边，一类边被称为主要边，而另一类被称为附加边。

Dark 有 N – 1 条主要边，并且 Dark 的任意两个节点之间都存在一条只由主要边构成的路径。

另外，Dark 还有 M 条附加边。

你的任务是把 Dark 斩为不连通的两部分。

一开始 Dark 的附加边都处于无敌状态，你只能选择一条主要边切断。

一旦你切断了一条主要边，Dark 就会进入防御模式，主要边会变为无敌的而附加边可以被切断。

但是你的能力只能再切断 Dark 的一条附加边。

现在你想要知道，一共有多少种方案可以击败 Dark。

注意，就算你第一步切断主要边之后就已经把 Dark 斩为两截，你也需要切断一条附加边才算击败了 Dark。

输入格式
第一行包含两个整数 N 和 M。

之后 N – 1 行，每行包括两个整数 A 和 B，表示 A 和 B 之间有一条主要边。

之后 M 行以同样的格式给出附加边。

输出格式
输出一个整数表示答案。

数据范围
N≤100000,M≤200000,数据保证答案不超过231−1
输入样例：
4 1
1 2
2 3
1 4
3 4
输出样例：
3

看到这道一般很难入手，不知道怎么去做。但是如果我们仔细分析，就会发现：

本来主要边形成了一棵树，如果没有附加边，那么我们随意砍断一条边，都会变得不连通。

但是我们加入了附加边，这就使得砍断一条边之后，当前这个被附加边相连，变得连通了。

我们画图可以发现，当加入一条附加边之后，这条附加边相当于把 a到b 的所有点相连起来了（因为相连就是使得 a到b 路径变成了一个环）。

所以我们发现，我们只要统计每条边是否被附加边覆盖，也就是是否被附加边相连，而且我们需要求出覆盖的次数。

覆盖一次：我们斩断这条主要边，再斩断这条覆盖主要边的附加边，所以答案加一。
覆盖零次：我们斩断这条主要边就已经不相连了，那么随便斩断一条附加边即可，所以答案加上m。

所以我们直接树上差分统计即可（边差分，注意讨论不是根节点的情况）。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,m,lg[N],f[N][30],h[N],p[N],res;
int head[N],nex[N*5],to[N*5],tot;
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void dfs(int x,int fa){
	h[x]=h[fa]+1;	f[x][0]=fa;
	for(int i=1;(1<<i)<=h[x];i++)	f[x][i]=f[f[x][i-1]][i-1];
	for(int i=head[x];i;i=nex[i]){
		if(to[i]!=fa)	dfs(to[i],x);
	}	
}
int lca(int x,int y){
	if(h[x]<h[y])	swap(x,y);
	while(h[x]>h[y])	x=f[x][lg[h[x]-h[y]]-1];
	if(x==y)	return x;
	for(int i=lg[h[x]]-1;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
void out(int x,int fa){
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==fa)	continue;
		out(to[i],x);
		p[x]+=p[to[i]];
	}
	if(!p[x]&&fa)	res+=m;
	else if(p[x]==1&&fa)	res++;	
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)	lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	for(int i=1;i<n;i++){
		int a,b;	scanf("%d %d",&a,&b);	add(a,b);	add(b,a);
	}
	dfs(1,0);
	for(int i=1;i<=m;i++){
		int a,b;	scanf("%d %d",&a,&b);	int c=lca(a,b);
		p[a]++;	p[b]++;	p[c]-=2;
	}
	out(1,0);
	cout<<res<<endl;
	return 0;
}