#include<bits/stdc++.h>
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define ll long long
#define lll __int128
#define fi first
#define se second
#define e emplace
#define eb emplace_back
#define db double
#define ef emplace_front
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vp vector<pii>
#define vt vector<tup>
#define all(x) x.begin(),x.end()
#define mp make_pair

#define FastI
#define FastO
//#define int ll
bool ST;
static const ll MOD=1e9+7,Phi=998244352,inv2=499122177,Root=3,iRoot=332748118;
static const ll inf=1073741823,Inf=4294967296,INF=4557430888798830399;
static const ld eps=1e-9,pi=3.1415926535;
char in[1<<20],*p1=in,*p2=in;
char out[1<<20],*p3=out;
using namespace std;
struct tup
{
	int x,y,z;
	tup(int X=0,int Y=0,int Z=0)
	{x=X,y=Y,z=Z;}
	bool operator <(const tup nd)const
	{return x<nd.x;}
};
#ifdef FastI
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#endif
#ifdef FastO
#define putchar(x) (p3-out==1<<20?fwrite(out,1,1<<20,stdout),p3=out,0:0,*p3++=x)
#define puts(x) write(x,'\n')
#endif
namespace FastIO
{
	template<typename T> inline void write(T x,char ch=' ')
	{
		if(is_same<char,T>::value)putchar(x);
		else
		{
			if(x<0)x=-x,putchar('-');
			static char st[25];
			int top=0;
			do st[top++]=x%10+'0',x/=10;while(x);
			while(top)putchar(st[--top]);
		}
		ch!='~'?putchar(ch):0;
	}
	inline void write(const char*x,char ch=' ')
	{
		for(int i=0;x[i]!='\0';++i)putchar(x[i]);
		ch!='~'?putchar(ch):0;
	}
	inline void read(char&s){do s=getchar();while(s=='\n'||s==' ');}
	inline void read(char s[])
	{
		int len=0;char st;
		do st=getchar();while(st=='\n'||st==' ');
		s[++len]=st,st=getchar();
		while(st!='\n'&&st!=' '&&st!='\r')s[++len]=st,st=getchar();
		s[++len]='\0';
	}
	template<typename T> inline void read(T &s)
	{
		char ch=getchar();s=0;
		while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
		bool tf=(ch=='-'&&(ch=getchar()));
		while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
		s=tf?-s:s;
	}
	inline void edl(){putchar('\n');}
	template<typename T1,typename T2> inline void read(pair<T1,T2> &s){read(s.fi),read(s.se);}
	template<typename T,typename...Args> inline void write(T x,Args...args){write(x,'~'),write(args...);}
	template<typename T,typename...Args> inline void read(T&x,Args&...args){read(x),read(args...);}
	#ifdef FastO
	struct Writer{~Writer(){fwrite(out,1,p3-out,stdout);}}Writ;
	#endif
}
using namespace FastIO;
namespace MTool
{
	inline int Cadd(int a,int b){return (ll)a+b>=MOD?(ll)a+b-MOD:a+b;}
	inline int Cdel(int a,int b){return a-b<0?a-b+MOD:a-b;}
	inline int Cmul(int a,int b){return 1ll*a*b%MOD;}
	inline int sqr(int a){return 1ll*a*a%MOD;}
	inline void Madd(int&a,int b){a=((ll)a+b>=MOD?(ll)a+b-MOD:a+b);}
	inline void Mdel(int&a,int b){a=(a-b<0?a-b+MOD:a-b);}
	inline void Mmul(int&a,int b){a=1ll*a*b%MOD;}
	inline int Cmod(int x){return (x%MOD+MOD)%MOD;}
	inline void Mmod(int&x){x=(x%MOD+MOD)%MOD;}
	template<typename T> inline bool Mmax(T&a,T b){return a<b?a=b,1:0;}
	template<typename T> inline bool Mmin(T&a,T b){return a>b?a=b,1:0;}
	template<typename...Args> inline void Madd(int&a,int b,Args...args){Madd(a,b),Madd(a,args...);}
	template<typename...Args> inline void Mmul(int&a,int b,Args...args){Mmul(a,b),Mmul(a,args...);}
	template<typename...Args> inline void Mdel(int&a,int b,Args...args){Mdel(a,b),Mdel(a,args...);}
	template<typename...Args> inline int Cadd(int a,int b,Args...args){return Cadd(Cadd(a,b),args...);}
	template<typename...Args> inline int Cmul(int a,int b,Args...args){return Cmul(Cmul(a,b),args...);}
	template<typename...Args> inline int Cdel(int a,int b,Args...args){return Cdel(Cdel(a,b),args...);}
	template<typename...Args,typename T> inline bool Mmax(T&a,T b,Args...args){return Mmax(a,b)|Mmax(a,args...);}
	template<typename...Args,typename T> inline bool Mmin(T&a,T b,Args...args){return Mmin(a,b)|Mmin(a,args...);}
	inline int power(int x,int y){int s=1;for(;y;y>>=1,Mmul(x,x))if(y&1)Mmul(s,x);return s;}
}
using namespace MTool;
namespace WrongAnswer_90
{
	int n,m;
	vi T[500010],ve[500010];
	vi add[500010],del[500010];
	int c[500010];
	pii a[500010];
	int ans[500010];
	
	namespace Tree
	{
		int tot,siz[500010],dep[500010],son[500010];
	    int top[500010],dfn[500010],id[500010],fa[500010];
	    inline int LCA(int x,int y)
	    {
	    	while(top[x]!=top[y])
	    	{
	    		if(dep[top[x]]>dep[top[y]])swap(x,y);
	    		y=fa[top[y]];
			}
			return dep[x]<dep[y]?x:y;
		}
	    void init()
		{
			for(int i=1;i<=n;++i)
			dep[i]=id[i]=dfn[i]=fa[i]=siz[i]=top[i]=son[i]=0;
			tot=0;
		    auto dfs0=[&](auto dfs0,int x,int Fa=0)->void
		    {
		        fa[x]=Fa,siz[x]=1;
		        dep[x]=dep[Fa]+1;
		        for(auto to:T[x])if(to!=Fa)
		        {
		            dfs0(dfs0,to,x),siz[x]+=siz[to];
		            if(siz[to]>siz[son[x]])son[x]=to;
		        }
		    };
		    auto dfs1=[&](auto dfs1,int x,int Top=1)->void
		    {
		        top[x]=Top;
				id[dfn[x]=++tot]=x;
		        if(son[x])dfs1(dfs1,son[x],Top);
		        for(auto to:T[x])if(to!=fa[x]&&to!=son[x])
		    	dfs1(dfs1,to,to);
		    };
	    	dfs0(dfs0,1),dfs1(dfs1,1);
		}
	}
	using namespace Tree;
	void dfs(int x)
	{
		for(auto to:T[x])if(to!=fa[x])
		dfs(to),c[x]+=c[to];
	}
	
	struct Delset
	{
	    int t[500010];
	    int top,st[500010];
	    void push(int x){st[++top]=x;}
	    void erase(int x){++t[x];}
	    void upd(){while(top&&t[st[top]])--t[st[top--]];}
	    int get(){return upd(),st[top];}
	}st[30];
	
	inline void modify(int x,int y,int z)
	{
		while(top[x]!=top[y])
		{
			if(dep[top[x]]>dep[top[y]])swap(x,y);
			del[top[y]].eb(z);
			add[y].eb(z);
			y=fa[top[y]];
		}
		if(dep[x]>dep[y])swap(x,y);
		add[y].eb(z);
	}
	void solve(int x,int dep=1)
	{
		if(x==1)cerr<<del[x].size()<<" "<<st[1].top<<" "<<st[1].st[3]<<' '<<st[1].get()<<endl;
		for(auto p:del[x])st[dep].erase(p);
		vi ers;
		for(auto id:ve[x])
		{
			ans[id]=st[dep].get();
			st[dep].erase(ans[id]);
			ers.eb(ans[id]);
			modify(a[id].fi,a[id].se,ans[id]);
		}
		if(son[x])
		{
			for(auto p:add[x])st[dep].push(p);
			solve(son[x],dep);
			for(auto p:add[x])st[dep].erase(p);
		}
		for(auto to:T[x])if(to!=fa[x]&&to!=son[x])
		solve(to,dep+1);
		
		for(auto p:ers)st[dep].push(p);
		for(auto p:del[x])st[dep].push(p);
	}
	
	void mian()
	{
		int x,y,lca;
		read(n,m);
		for(int i=1;i<=n;++i)
		{
			T[i].clear(),c[i]=0,ve[i].clear();
			add[i].clear(),del[i].clear();
		}
		for(int i=1;i<30;++i)
		{
			for(int j=1;j<=m;++j)st[i].t[j]=st[i].st[j]=0;
			st[i].top=0;
		}
		
		for(int i=1;i<n;++i)read(x,y),T[x].eb(y),T[y].eb(x);
		init();
		
		for(int i=1;i<=m;++i)
		{
			read(x,y),lca=LCA(x,y);
			++c[x],++c[y];
			--c[lca],--c[fa[lca]];
			a[i]=mp(x,y);
			ve[lca].eb(i);
		}
		
		dfs(1);
		int mx=-inf;
		for(int i=1;i<=n;++i)Mmax(mx,c[i]);
		
		for(int i=1;i<30;++i)for(int j=1;j<=mx;++j)st[i].push(j);
		solve(1);
		
		write(mx,'\n');
		for(int i=1;i<=m;++i)write(ans[i]);
		puts("");
	}
	inline void Mian()
	{
		int T=1,C;
		read(C,T);
		while(T--)mian();
	}
}
bool ED;
signed main()
{
//	ios::sync_with_stdio(0);
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	double st=clock();
	WrongAnswer_90::Mian();
	double ed=clock();
 	cerr<<endl;
 	cerr<<"Time: "<<ed-st<<" ms\n";
 	cerr<<"Memory: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB\n";
	return 0;
}