Distances

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

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)


	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: ACCEPTED

Test 2

Group: 2

Verdict: TIME LIMIT EXCEEDED