这是一篇直接交代码就能过的题解

虽然我不会证明任何东西，但是它就是跑得快！！1

具体做法：

发现 $2$ 的倍数非常多，占到了一半，先考虑将这棵树二分图染色。

容易发现黑白两色中至少有一种颜色个数超过一半，那么从这种颜色中随机选出一些按顺序填上 $2$ 的倍数。

然后将剩下的数 random_shuffle 一下，相当于随机顺序，按照这个顺序依次找到编号最小的能够填它的位置并填上。

如果不放心可以把编号也 random_shuffle 一下，不过我没这么做。

找到解的概率完全不会算，但是跑的飞快，300ms 不到就过了。

有一些优化方法可能可以跑得更快，但是可能会使代码不能看。

• 尽量将大质数填在度数大的节点上。

• 将更多小质数的倍数预先填上去，而不只是 $2$ 的倍数。

• random_shuffle 似乎不是均匀随机（?）可以手写一个出来。

• 交之前洗把脸。

代码：

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define pb push_back 
#define set(a,vl) memset(a,vl,sizeof(a))
int T,n,ord[N],a[N];bool col[N];set<int> z;
vector<int> vc1[2],e[N];
int gcd(int x,int y) {return y?gcd(y,x%y):x;}
void dfs(int u,int f)
{
	col[u]=col[f]^1;vc1[col[u]].pb(u);
	for(int i=0,v;i<e[u].size();++i)
	{v=e[u][i];if(v!=f) dfs(v,u);}
}
bool chk(int u,int x)
{
	for(int i=0,v;i<e[u].size();++i)
	{v=e[u][i];if(a[v] && gcd(x,a[v])>1) return 0;}return 1;
}
void upd(int u,int x) {a[u]=x;z.erase(u);}
bool slv1()
{
	ord[0]=0;set(a,0);z.clear();
	random_shuffle(vc1[0].begin(),vc1[0].end());
	for(int i=2;i<=n;i+=2) a[vc1[0][i/2-1]]=i;
	for(int i=1;i<=n;i+=2) ord[++ord[0]]=i; 
	random_shuffle(ord+1,ord+ord[0]+1);
	for(int i=1;i<=n;++i) if(!a[i]) z.insert(i); 
	for(int i=1,j;i<=ord[0];++i)
	{
		bool fl=0;
		for(set<int>::iterator it=z.begin();it!=z.end();++it)
		{j=*it;if(chk(j,ord[i])) {upd(j,ord[i]);fl=1;break;}}
		if(!fl) return 0;
	}return 1;
}
void slv()
{
	scanf("%d",&n);vc1[0].clear();vc1[1].clear();
	for(int i=1;i<=n;++i) e[i].clear();
	for(int i=1,u,v;i<n;++i)
		scanf("%d %d",&u,&v),e[u].pb(v),e[v].pb(u);dfs(1,0);
	if(vc1[0].size()<vc1[1].size()) swap(vc1[0],vc1[1]);
	while(1) if(slv1()) break;
	for(int i=1;i<=n;++i) printf("%d ",a[i]);puts("");
}
int main()
{
	srand(time(0));
	scanf("%d",&T);while(T--) slv();return 0;
}