#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 2000000
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int Ts,n,m,leng,smaxn,c[N+1],lg[N+1],dfn[N+1],fa[N+1],sz[N+1],top[N+1],hs[N+1],cl[N+1],depth[N+1];
bool used[N+1];
vector<int>E[N+1];
struct reads
{
	int x,y,num;
};
vector<reads>p[N+1];
struct rds
{
	int num,data;
};
vector<rds>v[N+1];
void add_edge(int x,int y)
{
	E[x].push_back(y),E[y].push_back(x);
	return;
}
void dfs(int x)
{
	used[x]=sz[x]=1;
	for (int i=0;i<E[x].size();++i)
		if (!used[E[x][i]])
		{
			fa[E[x][i]]=x,depth[E[x][i]]=depth[x]+1,dfs(E[x][i]),sz[x]+=sz[E[x][i]];
			if (sz[E[x][i]]>sz[hs[x]]) hs[x]=E[x][i];
		}
	return;
}
void dfs2(int x)
{
	dfn[x]=++leng;
	if (hs[x]) top[hs[x]]=top[x],dfs2(hs[x]);
	for (int i=0;i<E[x].size();++i)
		if (fa[E[x][i]]==x&&E[x][i]!=hs[x])
			top[E[x][i]]=E[x][i],dfs2(E[x][i]);
	return;
}
int lca(int x,int y)
{
	while (top[x]!=top[y])
	{
		if (depth[top[x]]<depth[top[y]]) swap(x,y);
		x=fa[top[x]];
	}
	if (depth[x]>depth[y]) swap(x,y);
	return x;
}
int tfa(int x,int y)
{
	int d=0;
	while (top[x]!=top[y]) d=top[x],x=fa[top[x]];
	if (x==y) return d;
	else return hs[y];
}
void cover(int l,int r,int d)
{
	v[l].push_back((rds){d,1}),v[r+1].push_back((rds){d,-1});
	return;
}
void adder(int x,int y,int z)
{
	while (top[x]!=top[y]) cover(dfn[top[x]],dfn[x],z),x=fa[top[x]];
	cover(dfn[y],dfn[x],z);
	return;
}
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int d)
{
	for (;x<=m;x+=lowbit(x)) c[x]+=d;
	return;
}
int get_rk(int x)
{
	int ps=0,res=0;
	for (int i=lg[m];i>=0;--i)
		if (ps+(1<<i)<=m&&res+c[ps+(1<<i)]<x)
			ps+=(1<<i),res+=c[ps];
	return ps+1;
}
void dfs3(int x)
{
	for (int i=0;i<v[dfn[x]].size();++i)
	{
		if (v[dfn[x]][i].data==1) add(v[dfn[x]][i].num,-1);
		else add(v[dfn[x]][i].num,1);
	}
	for (int i=0;i<p[x].size();++i)
	{
		cl[p[x][i].num]=get_rk(i+1);
		if (p[x][i].x!=x) adder(p[x][i].x,tfa(p[x][i].x,x),cl[p[x][i].num]);
		if (p[x][i].y!=x) adder(p[x][i].y,tfa(p[x][i].y,x),cl[p[x][i].num]);
	}
	if (hs[x]) dfs3(hs[x]);
	for (int i=0;i<E[x].size();++i)
		if (fa[E[x][i]]==x&&E[x][i]!=hs[x])
			dfs3(E[x][i]);
	return;
}
int main()
{
	int cs,x,y;
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
	cs=read(),Ts=read();
	while (Ts--)
	{
		n=read(),m=read(),leng=smaxn=0;
		for (int i=1;i<=n;++i) E[i].clear(),p[i].clear(),v[i].clear(),used[i]=hs[i]=fa[i]=0;
		for (int i=1;i<=m;++i) c[i]=1;
		for (int i=1;i<=m;++i)
			if (i+lowbit(i)<=m)
				c[i+lowbit(i)]+=c[i];
		for (int i=1;i<=n-1;++i) x=read(),y=read(),add_edge(x,y);
		depth[1]=1,dfs(1),top[1]=1,dfs2(1);
		for (int i=1;i<=m;++i) x=read(),y=read(),p[lca(x,y)].push_back((reads){x,y,i});
		dfs3(1);
		for (int i=1;i<=m;++i) smaxn=max(smaxn,cl[i]);
		printf("%d\n",smaxn);
		for (int i=1;i<=m;++i) printf("%d ",cl[i]);
		puts("");
	}
	return 0;
}