Distances

from random import shuffle
import sys
input = sys.stdin.readline

from functools import lru_cache

for _ in range(int(input())):
	N = int(input())
	adj = [[] for _ in range(N)]
	for _ in range(N-1):
		a, b = map(lambda s: int(s)-1, input().split())
		adj[a].append(b)
		adj[b].append(a)


	def f(i, prev):
		adj[i].remove(prev)
		for j in adj[i]: f(j, i)

	for j in adj[0]: f(j, 0)


	@lru_cache(maxsize=None)
	def f(i, step_up):
		a = adj[i]
		if len(a) == 0:
			return True, [i]

		if step_up == 3:
			return False, []

		ok, o = True, [i]
		for ai, j in enumerate(a):
			okr, ordr = f(j, 2 if ai != len(a)-1 else (step_up+1))
			ok &= okr
			o += ordr

		if ok:
			return True, o

		ok, o = True, []
		for ai, j in enumerate(a):
			okr, ordr = f(j, 2 if ai != len(a)-1 else 1)
			ok &= okr
			o += ordr

		return ok, o + [i]


	ok, o = f(0, 0)
	assert ok and len(o) == N
	print(' '.join(str(v+1) for v in o))
	continue



	@lru_cache(maxsize=None)
	def g(i, used, step_up):
		if used:
			o = [i]
			if step_up == 3:
				return len(adj[i]) == 0, o

			if len(adj[i]) == 1:
				ok, o2 = g(adj[i][0])




	D = [[-1] * N for _ in range(N)]
	A = [[] for _ in range(N)]
	for s in range(N):
		Q = [s]
		MD = D[s]
		MD[s] = 0
		for i in Q:
			for j in adj[i]:
				if MD[j] == -1:
					MD[j] = MD[i] + 1
					Q.append(j)

		for i in range(N):
			if 1 <= MD[i] <= 3:
				A[s].append(i)

		shuffle(A[s])


	V = [False] * N
	V[0] = True
	order = [0]

	def f(i):
		if len(order) == N:
			return True

		for j in A[i]:
			if not V[j]:
				V[j] = True
				order.append(j)
				if f(j): return True
				V[j] = False
				order.pop()

		return False

	f(0)

	print(' '.join(str(v+1) for v in order))

Test 1

Group: 1, 2

Verdict: WRONG ANSWER

Test 2

Group: 2

Verdict: WRONG ANSWER