#include<bits/stdc++.h>
using namespace std;

const int mod=1023456779;
int mi[10001],n,m,l,r,tp[2001],siz[2001],L[2001],R[2001],cnt,hd[2001],x,y,nw,po[2001],X,Y,fa[2001],xx;
struct node{int to,next;}e[4001];
pair<int,int> q[40000001];
int t[2001][5001];

void change(int i,int x)
{
	t[i][x=L[x]+2048]=1;
	for (x>>=1,cnt=1; x; x>>=1,cnt<<=1) 
		t[i][x]=(1ll*t[i][x<<1]*mi[cnt]+t[i][x<<1|1])%mod;
}

int find(int i,int I,int l,int r)
{
	l+=2048,r+=2048;
	if (t[i][l]!=t[I][l]) return po[l-2048];
	for (; l>1; l>>=1) 
		if (!(l&1)&&t[i][l+1]!=t[I][l+1])
		{
			for (l++; l<2048; l=(l<<1)|(t[i][l<<1]==t[I][l<<1]));
			return (l>r?0:po[l-2048]);
		}
	return 0;
}

void addedge(int x,int y)
{
	e[++cnt]=(node){y,hd[x]},hd[x]=cnt;
	e[++cnt]=(node){x,hd[y]},hd[y]=cnt;
}

void dfs(int x)
{
	siz[x]=1;
	for (int i=hd[x]; i; i=e[i].next)
		if (e[i].to!=fa[x]) fa[e[i].to]=x,dfs(e[i].to),siz[x]+=siz[e[i].to];
}

void Dfs(int x)
{
	L[x]=(++cnt),po[cnt]=x; int ma=0,maa;
	for (int i=hd[x]; i; i=e[i].next)
		if (e[i].to!=fa[x]&&siz[e[i].to]>ma) ma=siz[maa=e[i].to];
	if (!ma) {R[x]=cnt; return;}
	tp[maa]=tp[x],Dfs(maa);
	for (int i=hd[x]; i; i=e[i].next)
		if (e[i].to!=fa[x]&&e[i].to!=maa) tp[e[i].to]=e[i].to,Dfs(e[i].to);
	R[x]=cnt;
}

int main()
{
	mi[0]=1;
	for (int i=1; i<=10000; i++) mi[i]=mi[i-1]*2ll%mod;
	scanf("%d%d",&n,&m),cnt=0,memset(hd,0,sizeof(hd));
	for (int i=1; i<n; i++) scanf("%d%d",&x,&y),addedge(x,y);
	memset(po,0,sizeof(po)),cnt=0,dfs(1),tp[1]=1,Dfs(1),l=1,r=0;
	for (int i=1; i<=m; i++) scanf("%d%d",&x,&y),change(x,y),change(y,x),q[++r]=make_pair(x,y);
	while (l<=r)
	{
		x=q[l].first,y=q[l].second,l++;
		if (L[x]>L[y]) swap(x,y);
		if (R[x]>=L[y])
		{
			if (L[y]!=R[y])
			{
				while (nw=find(x,y,L[y]+1,R[y]))
				{
					if (!t[x][L[nw]+2048]) change(x,nw),change(nw,x),q[++r]=make_pair(x,nw);
					else change(y,nw),change(nw,y),q[++r]=make_pair(y,nw);
				}
			}
			if (L[x]>1)
			{
				while (nw=find(x,y,1,L[x]-1))
				{
					if (!t[x][L[nw]+2048]) change(x,nw),change(nw,x),q[++r]=make_pair(x,nw);
					else change(y,nw),change(nw,y),q[++r]=make_pair(y,nw);
				}
			}
			xx=y,X=fa[y],Y=x;
			while (tp[X]!=tp[Y])
			{
				while (nw=find(x,y,L[tp[X]],L[X]))
				{
					if (!t[x][L[nw]+2048]) change(x,nw),change(nw,x),q[++r]=make_pair(x,nw);
					else change(y,nw),change(nw,y),q[++r]=make_pair(y,nw);
				}
				xx=tp[X],X=fa[tp[X]];
			}
			if (X!=Y) 
			{
				while (nw=find(x,y,L[Y]+1,L[X]))
				{
					if (!t[x][L[nw]+2048]) change(x,nw),change(nw,x),q[++r]=make_pair(x,nw);
					else change(y,nw),change(nw,y),q[++r]=make_pair(y,nw);
				}
				xx=po[L[x]+1];
				if (R[xx]<n)
				{
					while (nw=find(x,y,R[xx]+1,n))
					{
						if (!t[x][L[nw]+2048]) change(x,nw),change(nw,x),q[++r]=make_pair(x,nw);
						else change(y,nw),change(nw,y),q[++r]=make_pair(y,nw);
					}
				}
			} else
			{
				if (L[x]+1<L[xx])
				{
					while (nw=find(x,y,L[x]+1,L[xx]-1))
					{
						if (!t[x][L[nw]+2048]) change(x,nw),change(nw,x),q[++r]=make_pair(x,nw);
						else change(y,nw),change(nw,y),q[++r]=make_pair(y,nw);
					}
				}
				if (R[xx]<n)
				{
					while (nw=find(x,y,R[xx]+1,n))
					{
						if (!t[x][L[nw]+2048]) change(x,nw),change(nw,x),q[++r]=make_pair(x,nw);
						else change(y,nw),change(nw,y),q[++r]=make_pair(y,nw);
					}
				}
			}
		} else
		{
			if (L[x]!=R[x])
			{
				while (nw=find(x,y,L[x]+1,R[x])) 
				{
					if (!t[x][L[nw]+2048]) change(x,nw),change(nw,x),q[++r]=make_pair(x,nw);
					else change(y,nw),change(nw,y),q[++r]=make_pair(y,nw);
				}
			}
			if (L[y]!=R[y])
			{
				while (nw=find(x,y,L[y]+1,R[y]))
				{
					if (!t[x][L[nw]+2048]) change(x,nw),change(nw,x),q[++r]=make_pair(x,nw);
					else change(y,nw),change(nw,y),q[++r]=make_pair(y,nw);
				}
			}
			X=fa[x],Y=fa[y];
			if (L[X]<L[Y]) swap(X,Y);
			while (tp[X]!=tp[Y])
			{
				while (nw=find(x,y,L[tp[X]],L[X]))
				{
					if (!t[x][L[nw]+2048]) change(x,nw),change(nw,x),q[++r]=make_pair(x,nw);
					else change(y,nw),change(nw,y),q[++r]=make_pair(y,nw);
				}
				X=fa[tp[X]];
				if (L[X]<L[Y]) swap(X,Y);
			}
			while (nw=find(x,y,L[Y],L[X]))
			{
				if (!t[x][L[nw]+2048]) change(x,nw),change(nw,x),q[++r]=make_pair(x,nw);
				else change(y,nw),change(nw,y),q[++r]=make_pair(y,nw);
			}
		}
	}
	return printf("%d\n",r),0;
}

Measured memory_bytes: 55680