#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int tid,T,n,m,a[N],b[N],s[N],mx,d[N],in[N],st[N],Tp,nw,ans[N];
int sz[N],dp[N],fa[N],son[N],tp[N],dfn[N],rev[N];
vector<int>e[N],vc[N],ad[N],dl[N],S;
void dfs1(int x){
	sz[x]=1;
	for(auto v:e[x])if(!sz[v]){
		dp[v]=dp[x]+1,fa[v]=x;
		dfs1(v);
		sz[x]+=sz[v];
		if(sz[v]>sz[son[x]])son[x]=v;
	}
}
void dfs2(int x,int t){
	tp[x]=t,dfn[x]=++dfn[0],rev[dfn[0]]=x;
	if(son[x])dfs2(son[x],t);
	for(auto v:e[x])if(!tp[v])dfs2(v,v);
}
int lca(int x,int y){
	for(int fx=tp[x],fy=tp[y];fx!=fy;x=fa[fx],fx=tp[x])if(dp[fx]<dp[fy])swap(x,y),swap(fx,fy);
	return dp[x]<dp[y]?x:y;
}
void dfs3(int x){
	for(auto v:e[x])if(v!=fa[x])dfs3(v),s[x]+=s[v];
	mx=max(mx,s[x]);
}
void ins(int x){
	++d[x];
	if(d[x]&&!in[x])in[x]=1,st[++Tp]=x;
}
void del(int x){
	--d[x];
}
int query(){
	while(!d[st[Tp]])in[st[Tp--]]=0;
	return st[Tp];
}
void cov(int l,int r,int k){
	if(l<=nw)del(k);
	else ad[l].emplace_back(k);
	if(r<nw)ins(k);
	else dl[r].emplace_back(k);
}
void upd(int x,int y,int k){
	for(int fx=tp[x],fy=tp[y];fx!=fy;x=fa[fx],fx=tp[x]){
		if(dp[fx]<dp[fy])swap(x,y),swap(fx,fy);
		cov(dfn[fx],dfn[x],k);
	}
	if(dp[x]<dp[y])swap(x,y);
	cov(dfn[y],dfn[x],k);
}
void solve(){
	scanf("%d%d",&n,&m);
	dfn[0]=mx=Tp=0;
	for(int i=1;i<=n;++i)e[i].clear(),vc[i].clear(),ad[i].clear(),dl[i].clear(),sz[i]=son[i]=tp[i]=s[i]=0;
	for(int i=1,x,y;i<n;++i){
		scanf("%d%d",&x,&y);
		e[x].emplace_back(y);
		e[y].emplace_back(x);
	}
	dfs1(1),dfs2(1,1);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&a[i],&b[i]);
		int c=lca(a[i],b[i]);
		++s[a[i]],++s[b[i]],--s[c],--s[fa[c]];
		vc[c].emplace_back(i);
	}
	dfs3(1);
	printf("%d\n",mx);
	for(int i=1;i<=mx;++i)d[i]=in[i]=0;
	for(int i=1;i<=mx;++i)ins(i);
	for(int i=1,u;i<=n;++i){
		for(auto v:ad[i])del(v);
		u=rev[i],nw=i;
		for(auto v:vc[u])upd(a[v],b[v],ans[v]=query());
		for(auto v:dl[i])ins(v);
	}
	for(int i=1;i<=m;++i)printf("%d%c",ans[i]," \n"[i==m]);
}
int main(){
	scanf("%d%d",&tid,&T);
	while(T--)solve();
	return 0;
}