题目链接：https://codeforces.com/contest/1605/problem/D

这是个昨晚的codeforces比赛题，不过我把它想难了233333，看到这种东西我先想到的是博弈论，然后还算SG函数。。。。看来是我想多了。今天睡醒起来后复盘才猜了一下，这东西有没有可能任意两点在重新打标签之后都无法同行，后来我举例试了一下确实可以。。。不过...我甜美的不知道这屌东西咋写。诶妈呀这可咋整啊

后来看了一下题解恍然大悟。首先我们定义MSB(i)=i的二进制下有多少位，如MSB(i)!=MSB(j)，则说明i号节点和j节点之间无法通行。那这个问题就转化成了重构这棵树，使得任意相邻节点MSB都不同。（不错，接下来怎么解决我当时就想不出来了）。接下来是把这棵树进行染色，使得任意相邻的两个节点所染的颜色不同，这一步有点类似于二分图的染色操作，可以递归式把这棵树任意相邻节点染成两种不同颜色。然后让MSB相同的节点无脑的塞到某一种颜色中，这样能保证它们之间肯定不相邻。。。emmm后边我表达能力有限，上代码吧

#include <bits/stdc++.h>
using namespace std;
int msb[200005];
vector<int>G[200005];
vector<int>color[2];
void init(){
	for(int i=1;i<=200000;i++){
		int cnt=0;
		for(int j=i;j;j/=2) cnt++;
		msb[i]=cnt-1;
	}
}
void paint(int now,int pa,int col){
	color[col].push_back(now);
	for(int v:G[now]){
		if(v==pa) continue;
		paint(v,now,col^1);
	}
}
int main(){
	init();
	int T;
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		vector<int>ans(n+5);
		vector<int>nodes[30];
		color[0].clear(),color[1].clear();
		for(int i=1;i<=n;i++){
			G[i].clear();
			nodes[msb[i]].push_back(i);
		}
		for(int i=1;i<n;i++){
			int u,v;
			cin>>u>>v;
			G[u].push_back(v),G[v].push_back(u);
		}
		paint(1,0,0);
		for(int i=21;i>=0;i--){
			int col=0;
			if(color[col^1].size()>color[col].size()) col^=1;
			for(int j:nodes[i]){
				ans[color[col].back()]=j;
				color[col].pop_back();
			}
		}
		for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
		cout<<endl;
	}
	return 0;
}