尝试构造使得树上任意两点间都不能互相到达，这样能达到答案的上界 \(n\)．（由于不能走动，所以先手永远必胜）

观察 \(u\oplus v\leq \min(u,v)\) 当且仅当 \(u,v\) 二进制下最高位相同。

假设 \(u<v\)，最高位为 \(k\)．如果最高位相同的话，\(u\oplus v\) 的最高位 \(<k\)，满足条件。如果最高位不同的话，\(u\oplus v\) 的最高位 \(=k\)，而 \(u\) 的最高位 \(<k\) 不满足条件。结论得证。

将最高位相同的视为一个颜色，那么性质是出现次数拉满的颜色不会小于 \(n/2\)，而且一定是 \(2^0,2^1,...2^k\) 这些颜色（因为 \(1+2+...+2^{k-1]=2^k-1\)）。

把节点按照 \(dep\) 奇偶性分成两部分，一定有一部分 \(\leq n/2\)，且两部分组成了二分图。

所以把这个 \(\leq n/2\) 的按照二进制填入对应的颜色，就能使得将一些颜色一个不漏地把二分图一边填满了。

剩下的就可以随便填了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define pb emplace_back
#define mp std::make_pair
#define fi first
#define se second
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef std::vector<int> vi;
typedef std::vector<ll> vll;
const ll mod = 998244353;
int Abs(int x) { return x < 0 ? -x : x; }
ll Add(ll x, ll y) { return (x+y>=mod) ? (x+y-mod) : (x+y); }
ll Mul(ll x, ll y) { return x * y % mod; }
ll Mod(ll x) { return x < 0 ? (x + mod) : (x >= mod ? (x-mod) : x); }
ll cadd(ll &x, ll y) { return x = (x+y>=mod) ? (x+y-mod) : (x+y); }
template <typename T> T Max(T x, T y) { return x > y ? x : y; }
template <typename T> T Min(T x, T y) { return x < y ? x : y; }
template <typename T>
T &read(T &r) {
	r = 0; bool w = 0; char ch = getchar();
	while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
	while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
	return r = w ? -r : r;
}
const int N = 1000010;
int n, dep[N], id[N];
vi eg[N];
vi v1, v2, vec[30];
void dfs(int x, int f) {
	dep[x] = dep[f] + 1;
	if(dep[x] & 1) v1.pb(x);
	else v2.pb(x);
	for(auto v : eg[x])
		if(v != f)
			dfs(v, x);
}
void solve() {
	read(n); v1.clear(); v2.clear();
	for(int i = 1; i <= n; ++i) dep[i] = 0, eg[i].clear();
	for(int i = 0; i <= 20; ++i) vec[i].clear();
	for(int i = 1; i <= n; ++i) {
		for(int j = 20; j >= 0; --j)
			if(i & (1 << j)) {
				vec[j].pb(i);
				break ;
			}
	}
	for(int i = 1, u, v; i < n; ++i) {
		read(u); read(v);
		eg[u].pb(v); eg[v].pb(u);
	}
	dfs(1, 0);
	if((int)v1.size() > (int)v2.size()) std::swap(v1, v2);
	int len = v1.size(), p = 0;
	for(int i = 0; i <= 20; ++i)
		if((int)vec[i].size() == (1 << i) && (1 << i) & len) {
			for(auto j : vec[i]) id[v1[p++]] = j;
			vec[i].clear();
		} p = 0;
	for(int i = 0; i <= 20; ++i)
		for(auto j : vec[i])
			id[v2[p++]] = j;
	for(int i = 1; i <= n; ++i) printf("%d ", id[i]);puts("");
}
signed main() {
	int T; read(T); while(T--) solve();return 0;
}