Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Chef is playing a video game. In a video game, there's a advanced civilization that has a total of N planets under control. All of those planets are connected with N-1 teleports in such a way, that it's possible to travel between any two planets using those teleports.

There's a chance that some planet gets infected. In this case it takes 24 hours for civilization to find out infection and prevent it from spreading. During this time infection uses teleport one time and infect all the planets that can be achieved in one teleport jump. So, once infection is detected at planet V, scientists already know that all planets connected to V via teleport are also infected. All the neccessary teleports are disabled right away and medics start working on eliminating the infection.
Each planet has population. Planets are numbered from 1 to N and their populations are P_{1}, P_{2}, ..., P_{N}. It is known that all the P_{i} are distinct.

There's a capital among all those planets. The capital is known to have the biggest population.
Once infection is detected at planet V, after disabling teleports on planet V and all connected to them, government has to establish a new capital if needed in the remaining not-infected planets. So, they list all the planets that are not connected to V and are not V. Then they pick the planet with biggest population. Your task is to find the number of this planet for every possible V.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains one integer N.
Next line contains N space-separated integers P_{1}, P_{2}, ..., P_{N} denoting the population of each planet.
Next N-1 lines contain two space-separated integers each V and U denoting that there's a teleport between planet V and U.

------ Output ------ 

For each test case, output a single line containing N integers A_{1}, A_{2}, ..., A_{N} separated by a space. Here A_{i} denotes the number of the planet picked to be new capital in case infection starts spreading from the planet i. In case infection affects all the planets output 0.

------ Constraints ------ 

$1 ≤ T ≤ 5$
$1 ≤ N ≤ 50000$
$1 ≤ P_{i} ≤ 10^{9}$
$All P_{i} are distinct$
$1 ≤ V ≤ N$
$1 ≤ U ≤ N$

------ Subtasks ------ 

$Subtask #1 (20 points): N ≤ 100$
$Subtask #2 (30 points): N ≤ 10000$
$Subtask #3 (50 points): No additional constraints$

----- Sample Input 1 ------ 
1
6
5 10 15 20 25 30
1 3
2 3
3 4
4 5
4 6
----- Sample Output 1 ------ 
6 6 6 2 6 5

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Data structures


Solutions:
t = int(input())
while t:
	n = int(input())
	p = [[int(i)] for i in input().split()]
	for i in range(n):
		p[i].append(i + 1)
	p.sort()
	p.reverse()
	connected = []
	for i in range(n + 1):
		connected.append([])
	for i in range(n - 1):
		(v, u) = [int(i) for i in input().split()]
		connected[v].append(u)
		connected[u].append(v)
	final = []
	for i in range(1, n + 1):
		infected = connected[i]
		ans = 0
		for j in p:
			if j[1] != i and j[1] not in infected:
				ans = j[1]
				flag = 1
				break
		final.append(ans)
	print(*final)
	t = t - 1


f = int(input())
for _ in range(f):
	n = int(input())
	planet_population = sorted([(0, 0)] + [(int(val), i + 1) for (i, val) in enumerate(input().split())])
	edges = [set() for i in range(n + 1)]
	for _ in range(n - 1):
		(v, u) = map(int, input().split())
		edges[v].add(u)
		edges[u].add(v)
	ans = ['0'] * n
	for i in range(1, n + 1):
		for j in range(n, 0, -1):
			if planet_population[i][1] == planet_population[j][1] or planet_population[j][1] in edges[planet_population[i][1]]:
				continue
			else:
				ans[planet_population[i][1] - 1] = str(planet_population[j][1])
				break
	print(' '.join(ans))


t = int(input())
for i in range(t):
	n = int(input())
	p = [[int(i)] for i in input().split()]
	for j in range(n):
		p[j].append(j + 1)
	p.sort()
	p.reverse()
	l = []
	for k in range(n + 1):
		l.append([])
	for z in range(n - 1):
		(v, u) = map(int, input().split())
		l[v].append(u)
		l[u].append(v)
	f = []
	for y in range(1, n + 1):
		c = l[y]
		ans = 0
		for g in p:
			if g[1] != y and g[1] not in c:
				ans = g[1]
				break
		f.append(ans)
	print(*f)


def capimove(edges, wts, wts_dict):
	for e in wts:
		if wts_dict[e] not in edges:
			return wts_dict[e]
	return 0
t = int(input())
for i in range(t):
	n = int(input())
	wts = [0] + [int(i) for i in input().split()]
	wts_dict = {wts[i]: i for i in range(1, n + 1)}
	wts.sort(reverse=True)
	adj = {i: [i] for i in range(1, n + 1)}
	for _ in range(n - 1):
		(i, j) = map(int, input().split())
		adj[i].append(j)
		adj[j].append(i)
	for k in range(1, n + 1):
		print(capimove(adj[k], wts, wts_dict), end=' ')
	print()


def capimove(A, popl, pop_dict, i):
	li = A[i]
	for el in popl:
		if pop_dict[el] not in li:
			return pop_dict[el]
	return 0
t = int(input())
for i in range(t):
	n = int(input())
	popl = [int(i) for i in input().split()]
	popl = [0] + popl
	pop_dict = {popl[i]: i for i in range(1, n + 1)}
	popl.sort(reverse=True)
	A = {i: [i] for i in range(1, n + 1)}
	for _ in range(n - 1):
		(i, j) = map(int, input().split())
		if i not in A[j] or j not in A[i]:
			A[i].append(j)
			A[j].append(i)
	for k in range(1, n + 1):
		print(capimove(A, popl, pop_dict, k), end=' ')
	print('')


T = int(input())
for i in range(T):
	n = int(input())
	populations = [0]
	populations.extend([int(i) for i in input().split()])
	d = {populations[i]: i for i in range(1, n + 1)}
	ports = {}
	populations.sort(reverse=True)
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		if u in ports.keys():
			ports[u].append(v)
		else:
			ports[u] = [v, u]
		if v in ports.keys():
			ports[v].append(u)
		else:
			ports[v] = [u, v]
	for i in range(1, n + 1):
		out = 0
		s = ports[i]
		for j in populations:
			if d[j] not in s:
				out = d[j]
				break
		print(out, end=' ')
	print('')


from heapq import *
for case in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	d = {}
	path = []
	for i in range(N):
		d[L[i]] = i
		path.append(set([i]))
	L.sort(reverse=True)
	for i in range(N - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		path[a].add(b)
		path[b].add(a)
	o = ''
	for i in range(N):
		s = path[i]
		f = True
		for j in L:
			if d[j] not in s:
				o += str(d[j] + 1) + ' '
				f = False
				break
		if f:
			o += '0 '
	print(o)


t = int(input())
for _t in range(t):
	n = int(input())
	x = [int(y) for y in input().split()]
	adj = [[i] for i in range(n)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u - 1].append(v - 1)
		adj[v - 1].append(u - 1)
	heap = [(x[i], i) for i in range(len(x))]
	heap.sort()
	for node in range(n):
		keep = []
		while heap[-1][1] in adj[node]:
			keep.append(heap[-1])
			heap.pop()
		print(heap[-1][1] + 1 if len(heap) else 0, end=' ')
		while len(keep):
			heap.append(keep[-1])
			keep.pop()
	print('\n')


from copy import copy
for _ in range(int(input())):
	N = int(input())
	a = list(map(int, input().split()))
	aa = [[a[i], i] for i in range(N)]
	aa.sort()
	order = [aa[i][1] for i in range(N)]
	conn = [[i] for i in range(N)]
	for i in range(N - 1):
		(u, v) = map(int, input().split())
		conn[u - 1].append(v - 1)
		conn[v - 1].append(u - 1)
	result = []
	for i in range(N):
		connectedTo = conn[i]
		notFound = True
		t = N - 1
		if len(connectedTo) == N:
			t = -1
		while notFound and t >= 0:
			if order[t] in connectedTo:
				t -= 1
			else:
				notFound = False
		if notFound:
			result.append(0)
		else:
			result.append(order[t] + 1)
	print(*result)


T = int(input())
for x in range(T):
	N = int(input())
	P = [[int(popu)] for popu in input().split()]
	for i in range(N):
		P[i].append(i + 1)
	P.sort(reverse=True)
	conn = dict()
	for y in range(N - 1):
		(a, b) = [int(k) for k in input().split()]
		if a in conn.keys():
			conn[a].append(b)
		else:
			conn[a] = [b]
		if b in conn.keys():
			conn[b].append(a)
		else:
			conn[b] = [a]
	ans = [0] * N
	for i in range(N):
		temp = conn[i + 1]
		temp.append(i + 1)
		for j in P:
			if j[1] not in temp:
				ans[i] = j[1]
				break
	print(*ans, sep=' ')


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	population = {}
	for i in range(n):
		population[i] = arr[i]
	adjancecy_list = {}
	for edges in range(n - 1):
		(u, v) = map(int, input().split())
		(u, v) = (u - 1, v - 1)
		try:
			adjancecy_list[u][v] = 1
		except KeyError:
			adjancecy_list[u] = {}
			adjancecy_list[u][v] = 1
		try:
			adjancecy_list[v][u] = 1
		except KeyError:
			adjancecy_list[v] = {}
			adjancecy_list[v][u] = 1
	arr = sorted(population.items(), key=lambda kv: (kv[1], kv[0]), reverse=True)
	for i in range(n):
		neighbours = adjancecy_list[i]
		flag = True
		for (node, pop) in arr:
			if node != i:
				try:
					temp = neighbours[node]
				except KeyError:
					print(node + 1, end=' ')
					flag = False
					break
		if flag:
			print(0, end=' ')
	print()


for __ in range(int(input())):
	N = int(input())
	arr = [(0, 0)] + [(int(val), i + 1) for (i, val) in enumerate(input().split())]
	edges = [set() for i in range(N + 1)]
	for _ in range(N - 1):
		(v, u) = map(int, input().split())
		edges[v].add(u)
		edges[u].add(v)
	arr.sort()
	ans = [0] * N
	for i in range(1, N + 1):
		for j in range(N, 0, -1):
			if arr[i][1] == arr[j][1] or arr[j][1] in edges[arr[i][1]]:
				continue
			else:
				ans[arr[i][1] - 1] = arr[j][1]
				break
	print(*ans)


from sys import stdin
from collections import defaultdict
t = int(stdin.readline())
for _ in range(t):
	N = int(stdin.readline())
	planets_population = list(map(int, stdin.readline().strip().split(' ')))
	planets = []
	for i in range(1, N + 1):
		planets.append((planets_population[i - 1], i))
	planets.sort()
	infected_planets_dict = defaultdict(list)
	infected_planets = []
	for i in range(N - 1):
		infected_planets.append(tuple(map(int, stdin.readline().strip().split(' '))))
	for (v, u) in infected_planets:
		if v in infected_planets_dict:
			ne = infected_planets_dict[v]
			ne.add(u)
			infected_planets_dict[v] = ne
		else:
			infected_planets_dict[v] = set([v, u])
		if u in infected_planets_dict:
			ne = infected_planets_dict[u]
			ne.add(v)
			infected_planets_dict[u] = ne
		else:
			infected_planets_dict[u] = set([u, v])
	ans = []
	for v in range(1, N + 1):
		connected_planets = infected_planets_dict[v]
		k = len(planets)
		while k > 0:
			current_planet = planets[k - 1]
			if current_planet[1] not in connected_planets:
				ans.append(current_planet[1])
				break
			k -= 1
	for i in ans:
		print(i, end=' ')


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	links = dict([(i, set([i])) for i in range(n)])
	for i in range(n - 1):
		(v, u) = map(int, input().split())
		links[u - 1].add(v - 1)
		links[v - 1].add(u - 1)
	inds = [i for i in range(0, n)]
	inds.sort(reverse=True, key=lambda x: p[x])
	ans = [set(inds)]
	for i in range(0, n - 1):
		overlap = links[inds[i]].intersection(ans[i])
		ans[i] -= overlap
		if len(overlap) == 0:
			break
		ans.append(overlap.copy())
	if len(ans) == n:
		if inds[n - 1] in ans[n - 1]:
			ans[n - 1].subtract(inds[n - 1])
	finalans = [0] * n
	for i in range(len(ans)):
		for j in ans[i]:
			finalans[j] = inds[i] + 1
	print(' '.join([str(x) for x in finalans]))


import heapq
t = int(input())
while t != 0:
	n = int(input())
	a = list(map(int, input().split()))
	h = []
	hs = []
	ans = []
	d = {}
	for i in range(n):
		heapq.heappush(h, -a[i])
		ht = []
		ht.append(-a[i])
		hs.append(ht)
		d[-a[i]] = i + 1
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		heapq.heappush(hs[u - 1], -a[v - 1])
		heapq.heappush(hs[v - 1], -a[u - 1])
	for i in range(n):
		pop = []
		flag = 0
		while len(hs[i]) > 0:
			toph = heapq.heappop(h)
			pop.append(toph)
			tophs = heapq.heappop(hs[i])
			if toph != tophs:
				ans.append(toph)
				flag = 1
				break
		if flag == 0 and len(h) == 0:
			ans.append(0)
		elif flag == 0 and len(h) > 0:
			toph = heapq.heappop(h)
			pop.append(toph)
			ans.append(toph)
		for j in pop:
			heapq.heappush(h, j)
	for i in ans:
		print(d[i], end=' ')
	print('')
	t -= 1


t = int(input())
for _ in range(t):
	N = int(input())
	weights = [[int(x)] for x in input().split()]
	for i in range(N):
		weights[i].append(i + 1)
	weights.sort(reverse=True)
	l1 = {}
	for i in range(N - 1):
		(q1, q2) = [int(x) for x in input().split()]
		if q1 in l1.keys():
			l1[q1].append(q2)
		else:
			l1[q1] = [q2]
		if q2 in l1.keys():
			l1[q2].append(q1)
		else:
			l1[q2] = [q1]
	l2 = [0] * N
	for i in range(N):
		r = l1[i + 1]
		r.append(i + 1)
		for item in weights:
			if item[1] not in r:
				l2[i] = item[1]
				break
	for ans in l2:
		print(ans, end=' ')


for _ in range(int(input())):
	n = int(input())
	p = [0] + list(map(int, input().split()))
	popnum = [(p[i], i) for i in range(1, n + 1)]
	popnum.sort(reverse=True)
	adj = [[] for u in range(n)]
	for i in range(n - 1):
		(v, u) = map(int, input().split())
		adj[v - 1].append(u)
		adj[u - 1].append(v)
	for i in range(n):
		top = 0
		while popnum[top][1] in adj[i] or popnum[top][1] == i + 1:
			top += 1
		print(popnum[top][1], end=' ')
	print()


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	d = {}
	b = []
	for i in range(n):
		b.append([l[i], i])
	b.sort(key=lambda x: x[0], reverse=True)
	d = defaultdict(list)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		u = u - 1
		v = v - 1
		d[u].append(v)
		d[v].append(u)
	for i in range(n):
		d[i] = d[i] + [i]
	for i in range(n):
		for j in range(n):
			if b[j][1] not in d[i]:
				print(b[j][1] + 1, end=' ')
				break
		else:
			print(0, end=' ')


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	la = [[l[i], i] for i in range(n)]
	hash = defaultdict(list)
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		hash[a].append(b)
		hash[b].append(a)
	la.sort(reverse=True)
	for i in range(n):
		k = {l[j - 1] for j in hash[i + 1]}
		k.add(l[i])
		for j in range(n):
			if la[j][0] not in k:
				print(la[j][1] + 1, end=' ')
				break


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	s = set()
	p = [[i, int(v)] for (i, v) in enumerate(input().split())]
	p.sort(key=lambda x: x[1], reverse=True)
	g = defaultdict(list)
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		g[u].append(v)
		g[v].append(u)
	for i in range(n):
		for j in range(n):
			if p[j][0] not in [*g[i], i]:
				print(p[j][0] + 1, end=' ')
				break
	print()


import sys
from operator import *

def solve(pop1, pop2, n, adj):
	pop = pop1
	d = dict()
	for i in range(n):
		d[pop[i]] = i + 1
	pop2.sort(reverse=True)
	A = [0] * n
	for i in range(n):
		l = len(adj[i])
		s = set()
		s.add(pop1[i])
		for k in range(l):
			s.add(pop1[adj[i][k]])
		for j in range(n):
			if pop2[j] not in s:
				A[i] = d[pop2[j]]
				break
	return A

def Main():
	t = int(sys.stdin.readline())
	while t > 0:
		n = int(sys.stdin.readline())
		population = sys.stdin.readline().split()
		pop1 = [0] * n
		pop2 = [0] * n
		for i in range(n):
			pop1[i] = int(population[i])
			pop2[i] = int(population[i])
		adj = [[] for i in range(n)]
		for i in range(1, n):
			(u, v) = map(int, sys.stdin.readline().split())
			u = u - 1
			v = v - 1
			adj[u].append(v)
			adj[v].append(u)
		result = solve(pop1, pop2, n, adj)
		print(*result, sep=' ')
		t = t - 1
Main()


from operator import *

def solve(adj, population, n) -> 'list':
	pop_city = [[p, i] for (i, p) in enumerate(population, 1)]
	pop_city.sort(reverse=True)
	ans = [0] * n
	for i in range(n):
		removed = {population[node] for node in adj[i]}
		removed.add(population[i])
		for j in range(n):
			if pop_city[j][0] not in removed:
				ans[i] = pop_city[j][1]
				break
	return ans

def Main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		population = list(map(int, input().rstrip().split()))
		adj = [[] for i in range(n)]
		for i in range(n - 1):
			(u, v) = list(map(int, input().rstrip().split()))
			u -= 1
			v -= 1
			adj[u].append(v)
			adj[v].append(u)
		res = solve(adj, population, n)
		print(*res, sep=' ')
Main()


for _ in range(int(input())):
	n = int(input())
	z = input().split()
	popn = list(map(int, z[:n]))
	popn.insert(0, 0)
	links = [[] for i in range(n + 1)]
	for e in range(n - 1):
		z = input().split()
		(fr, to) = map(int, z[:2])
		links[fr].append(to)
		links[to].append(fr)
	poprf = list(range(1, n + 1))
	poprf.sort(reverse=True, key=lambda x: popn[x])
	cap = poprf.pop(0)
	cloc = [cap] + links[cap]
	tmpcap = [cap] * (n + 1)
	alt = poprf[0]
	aloc = links[alt]
	altopt = [alt]
	if alt in cloc:
		ctown = ptown = outtown = False
		for t in poprf[1:]:
			if t in cloc:
				if not ctown:
					altopt.append(t)
					ctown = True
			elif t in aloc:
				if not ptown:
					altopt.append(t)
					ptown = True
			else:
				altopt.append(t)
				break
			if ctown and ptown:
				break
	else:
		comm = set(cloc) & set(aloc)
		if len(comm) > 0:
			cm = comm.pop()
			cmloc = [cm] + links[cm]
			for t in poprf[1:]:
				if t not in cmloc:
					altopt.append(t)
					break
	for loc in cloc:
		qloc = [loc] + links[loc]
		for t in altopt:
			if t not in qloc:
				tmpcap[loc] = t
				break
	print(*tmpcap[1:])


def heap_decap(hp, ref):
	elm = hp.pop()
	rfelm = ref[elm]
	hplen = len(hp)
	a = 0
	b = 2 * a + 1
	while b < hplen:
		if b + 1 < hplen:
			if ref[hp[b + 1]] > ref[hp[b]]:
				b += 1
		if ref[hp[b]] > rfelm:
			hp[a] = hp[b]
			a = b
			b = 2 * a + 1
		else:
			break
	hp[a] = elm
for _ in range(int(input())):
	n = int(input())
	z = input().split()
	popn = list(map(int, z[:n]))
	popn.insert(0, 0)
	links = [[] for i in range(n + 1)]
	for e in range(n - 1):
		z = input().split()
		(fr, to) = map(int, z[:2])
		links[fr].append(to)
		links[to].append(fr)
	poprf = list(range(1, n + 1))
	poprf.sort(reverse=True, key=lambda x: popn[x])
	cap = poprf.pop(0)
	cpop = popn[cap]
	cloc = [cap] + links[cap]
	prox = cloc[1:]
	prox.sort(reverse=True, key=lambda x: popn[x])
	pcap = prox[0]
	ploc = links[pcap]
	ctown = ptown = outtown = 0
	for e in range(len(poprf)):
		if poprf[e] in cloc:
			ctown += 1
		elif poprf[e] in ploc:
			ptown += 1
		else:
			outtown += 1
		if ctown > 1 and ptown > 0 or (ctown > 0 and outtown > 0):
			poprf = poprf[:e + 1]
			break
	tcap = [cap] * (n + 1)
	for loc in cloc:
		qloc = [loc] + links[loc]
		popwk = poprf[:]
		while popwk[0] in qloc:
			heap_decap(popwk, popn)
		tcap[loc] = popwk[0]
	print(*tcap[1:])


from heapq import *
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	arr = [-1] + list(map(int, input().split()))
	hmap = {}
	heap = []
	for i in range(1, n + 1):
		hmap[arr[i]] = i
		heappush(heap, -arr[i])
	graph = defaultdict(set)
	for i in range(n - 1):
		(v, u) = list(map(int, input().split()))
		graph[arr[v]].add(arr[u])
		graph[arr[u]].add(arr[v])
	ans = []
	for i in range(1, n + 1):
		toadd = []
		while -heap[0] == arr[i] or -heap[0] in graph[arr[i]]:
			toadd.append(heap[0])
			heappop(heap)
		ans.append(hmap[-heap[0]])
		for i in toadd:
			heappush(heap, i)
	print(' '.join(map(str, ans)))


import gc
gc.disable()

def main():
	from sys import stdin, stdout
	import atexit, io, sys
	buffer = io.StringIO()
	sys.stdout = buffer

	@atexit.register
	def write():
		sys.__stdout__.write(buffer.getvalue())
	t = int(stdin.readline())
	dec = [False for x in range(50000 + 1)]
	while t:
		t -= 1
		n = int(stdin.readline())
		pop = [[int(x), y] for (x, y) in zip(stdin.readline().split(), range(1, n + 1))]
		pop.sort(reverse=True)
		conn = [set() for x in range(n + 1)]
		for x in range(n - 1):
			(a, b) = map(int, stdin.readline().split())
			conn[a].add(b)
			conn[b].add(a)
		ans = ''
		for x in range(1, n + 1):
			conn[x].add(x)
			for w in range(len(pop)):
				if pop[w][1] not in conn[x]:
					ans += str(pop[w][1]) + ' '
					break
			else:
				ans += '0 '
		stdout.write('{}\n'.format(ans))
main()


q = int(input())
while q:
	n = int(input())
	l = list(map(int, input().split()))
	l[n:] = []
	L = [[l[i], i] for i in range(n)]
	L.sort()
	c = {}
	for i in range(n - 1):
		(v, u) = map(int, input().split())
		if v - 1 in c:
			c[v - 1].append(u - 1)
		else:
			c[v - 1] = [v - 1, u - 1]
		if u - 1 in c:
			c[u - 1].append(v - 1)
		else:
			c[u - 1] = [u - 1, v - 1]
	for i in range(n):
		flag = 0
		for j in range(n - 1, -1, -1):
			if L[j][1] not in c[i]:
				flag = 1
				break
		if flag == 1:
			print(L[j][1] + 1, end=' ')
		else:
			print(0, end=' ')
	print()
	q = q - 1


from sys import stdin
import heapq
T = int(stdin.readline().strip())
while T > 0:
	N = int(stdin.readline().strip())
	popN1 = [0] + [int(n) for n in stdin.readline().strip().split()]
	popN = [(popN1[i], i) for i in range(1, N + 1)]
	popN.sort()
	dict1 = {i: [i] for i in range(1, N + 1)}
	for _ in range(1, N):
		[U, V] = [int(n) for n in stdin.readline().strip().split()]
		dict1[U].append(V)
		dict1[V].append(U)
	for i in range(1, N + 1):
		index1 = 0
		for j in range(N - 1, -1, -1):
			if popN[j][1] not in dict1[i]:
				index1 = popN[j][1]
				break
		print(index1, end=' ')
	T -= 1


t = int(input())
dec = [False for x in range(50000 + 1)]
while t > 0:
	t -= 1
	n = int(input())
	pop = [[int(x), y] for (x, y) in zip(input().split(), range(1, n + 1))]
	pop.sort(reverse=True)
	conn = [set() for x in range(n + 1)]
	for x in range(n - 1):
		(a, b) = map(int, input().split())
		conn[a].add(b)
		conn[b].add(a)
	for x in range(1, n + 1):
		conn[x].add(x)
		for w in range(len(pop)):
			if pop[w][1] not in conn[x]:
				print(pop[w][1], end=' ')
				break
		else:
			print(0, end=' ')
	print()


import copy

class Graph:
	V = 0
	adj_list = []
	p = []
	mmx = 0
	index = 0
	w = []

	def __init__(self, V):
		del self.p[:]
		del self.adj_list[:]
		del self.w[:]
		self.V = V
		self.p = list(map(int, input().split()))
		for i in range(0, len(self.p)):
			self.w.append([self.p[i], i])
		for i in range(0, V):
			self.adj_list.append([i])

	def add_Edge(self, u, v):
		self.adj_list[u].append(v)
		self.adj_list[v].append(u)

	def solve(self):
		pp = sorted(self.w, key=lambda l: l[0], reverse=True)
		for i in range(0, self.V):
			q = 0
			while q < n:
				self.index = pp[q][1]
				if self.index not in self.adj_list[i]:
					print(self.index + 1, end=' ')
					break
				else:
					q += 1
				if q == n - 1:
					print('0', end=' ')
		print()
t = int(input())
for _ in range(0, t):
	n = int(input())
	g = Graph(n)
	for __ in range(0, n - 1):
		(u, v) = map(int, input().split())
		u = u - 1
		v = v - 1
		g.add_Edge(u, v)
	g.solve()


from collections import defaultdict
from bisect import bisect_left

class City:

	def __init__(self, pop, num):
		self.pop = pop
		self.num = num

def solve():
	t = int(input())
	for i in range(t):
		find_capitals()

def find_capitals():
	ans = []
	n = int(input())
	cities = [City(int(pop), i + 1) for (i, pop) in enumerate(input().split())]
	cities.sort(key=lambda x: x.pop, reverse=True)
	graph = defaultdict(list)
	for i in range(n - 1):
		(l, r) = [int(j) for j in input().split()]
		graph[l].append(r)
		graph[r].append(l)
	for i in range(1, n + 1):
		graph[i].sort()
	for i in range(1, n + 1):
		for city in cities:
			possible_pos = bisect_left(graph[i], city.num)
			is_present_in_adj_list = graph[i][possible_pos] == city.num if possible_pos < len(graph[i]) else False
			if city.num != i and (not is_present_in_adj_list):
				ans.append(city.num)
				break
	ans_str = ''
	for i in ans:
		ans_str += str(i) + ' '
	ans_str.rstrip()
	print(ans_str)
solve()


for t in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	p = []
	for (i, ai) in enumerate(a):
		p.append([i + 1, ai])
	p.sort(key=lambda ai: ai[1], reverse=True)
	neighbors = [None]
	for i in range(n):
		neighbors.append(list())
	for i in range(n - 1):
		e = [int(i) for i in input().split()]
		neighbors[e[0]].append(e[1])
		neighbors[e[1]].append(e[0])
	unsolved = set(range(1, n + 1))
	solution = dict()
	i = 0
	while unsolved:
		c = p[i][0]
		here = {c}
		here.update(set(neighbors[c]))
		solving = unsolved - here
		for k in solving:
			unsolved.remove(k)
			solution[k] = c
		i += 1
	final = [str(solution[i]) for i in range(1, n + 1)]
	toprint = ' '.join(final)
	print(toprint)


def search(a, lower, x, high):
	mid = (high + lower) // 2
	if lower <= high:
		if a[mid] == x:
			return True
		elif a[mid] > x:
			return search(a, lower, x, mid - 1)
		else:
			return search(a, mid + 1, x, high)
	else:
		return False
import bisect
from operator import itemgetter
for i in range(int(input())):
	b = int(input())
	a = list(map(int, input().split()))
	v = []
	for j in range(b - 1):
		ca = list(map(int, input().split()))
		v.append([ca[0], ca[1]])
		v.append([ca[1], ca[0]])
	r = []
	for j in range(b):
		r.append([a[j], j + 1])
	r.sort(key=itemgetter(0))
	u = []
	for em in r:
		u.append(em[1])
	v.sort(key=itemgetter(0, 1))
	v.reverse()
	x = []
	for j in range(b):
		x.append(0)
	t = 0
	for j in range(2 * (b - 1)):
		ba = b - 1
		if v[j][0] != t:
			if j < 2 * b - 3:
				sa = []
				while j < 2 * b - 3 and v[j][0] == v[j + 1][0] and (ba >= 0):
					sa.append(v[j][1])
					j += 1
					r = j
				sa.append(v[j][1])
				sa.reverse()
				bisect.insort_left(sa, v[j][0], lo=0, hi=len(sa))
				mad = False
				while True:
					if ba >= 0:
						if search(sa, 0, u[ba], len(sa) - 1) == True:
							ba -= 1
							ram = ba
						else:
							break
					if ba == -1:
						mad = True
						break
				if mad == True:
					x[v[j][0] - 1] = -1
				if mad == False:
					x[v[j][0] - 1] = u[ba]
			if j == 2 * b - 3:
				if v[j][0] == u[ba]:
					ba -= 1
				if v[j][1] == u[ba]:
					ba -= 1
				if v[j][0] == u[ba]:
					ba -= 1
				x[v[j][0] - 1] = u[ba]
		t = v[j][0]
	for j in range(b):
		if x[j] == 0:
			if j + 1 != u[b - 1]:
				x[j] = u[b - 1]
			else:
				x[j] = u[b - 2]
		if x[j] == -1:
			x[j] = 0
	for j in range(b):
		print(x[j], end=' ')
	print()


def main():
	from sys import stdin, stdout
	import collections
	for _ in range(int(stdin.readline())):
		n = int(stdin.readline())
		p = tuple(map(int, stdin.readline().split()))
		newp = [(p[x], x + 1) for x in range(n)]
		newp.sort(reverse=True, key=lambda x: x[0])
		e = collections.defaultdict(set)
		for _ in range(n - 1):
			(a, b) = map(int, stdin.readline().split())
			e[a - 1].add(b - 1)
			e[a - 1].add(a - 1)
			e[b - 1].add(a - 1)
			e[b - 1].add(b - 1)
		for i in range(n):
			for x in range(n):
				if newp[x][1] - 1 not in e[i]:
					break
			stdout.write(str(newp[x][1]) + ' ')
		stdout.write('\n')
main()


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	p_index = dict()
	for j in range(n):
		p_index[p[j]] = j
	adj_matrix = [set() for _ in range(n)]
	for j in range(n - 1):
		(u, v) = list(map(int, input().split()))
		u -= 1
		v -= 1
		adj_matrix[u].add(p[v])
		adj_matrix[v].add(p[u])
	for j in range(n):
		adj_matrix[j].add(p[j])
	temp_ans = ''
	p.sort()
	for j in range(n):
		flag = 0
		idx = -1
		for k in range(n - 1, -1, -1):
			if p[k] not in adj_matrix[j]:
				flag = 1
				idx = p_index[p[k]]
				break
		if flag == 0:
			temp_ans += '0 '
		else:
			temp_ans += str(idx + 1) + ' '
	ans.append(temp_ans)
for x in ans:
	print(x)


from collections import defaultdict
in_capital = [1 for i in range(0, 50001)]
t = int(input())
for testcases in range(0, t):
	nodes = int(input())
	graph = defaultdict(list)
	for i in range(1, nodes + 1):
		graph[i].append(i)
	populations = list(map(int, input().split(' ')))
	for i in range(1, nodes):
		(a, b) = map(int, input().split(' '))
		graph[a].append(b)
		graph[b].append(a)
	sortpop = [(0, 0)]
	for i in range(1, nodes + 1):
		sortpop.append((populations[i - 1], i))
	sortpop.sort(reverse=True)
	capitals = [i[1] for i in sortpop]
	for (pos, i) in enumerate(range(1, nodes + 1)):
		if len(graph[i]) == nodes:
			if pos == nodes - 1:
				print('0')
			else:
				print('0', end=' ')
		else:
			for elem in graph[i]:
				in_capital[elem] = 0
			for elem in capitals:
				if in_capital[elem] == 1:
					if pos == nodes - 1:
						print(elem)
					else:
						print(elem, end=' ')
					break
				else:
					pass
			for elem in graph[i]:
				in_capital[elem] = 1


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	p = list(reversed(sorted(((int(x), i) for (i, x) in enumerate(input().split())))))
	edges = defaultdict(set)
	for _ in range(n - 1):
		(u, v) = [int(x) - 1 for x in input().split()]
		edges[u].add(v)
		edges[v].add(u)
	a = []
	for i in range(n):
		for (x, j) in p:
			if i != j and j not in edges[i]:
				a.append(j)
				break
		else:
			a.append(-1)
	print(' '.join((str(x + 1) for x in a)))


def solve(pp, tree):
	return next((p[0] for p in pp if p[0] not in tree))
T = int(input())
for t in range(T):
	n = int(input())
	pp = list(enumerate(map(int, input().split())))
	pp.sort(key=lambda z: z[1], reverse=True)
	tree = [set([i]) for i in range(n)]
	for i in range(n - 1):
		(u, v) = map(lambda x: int(x) - 1, input().split())
		tree[u].add(v)
		tree[v].add(u)
	res = list(map(lambda x: solve(pp, tree[x]) + 1, range(n)))
	print(*res)


t = int(input())
for _ in range(t):
	n = int(input())
	p = map(int, input().split())
	p = list(p)
	l = []
	for i in range(n):
		l.append([p[i], i + 1])
	l.sort(reverse=True)
	d = dict()
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		d[u, v] = 1
		d[v, u] = 1
	s = set(range(0, n))
	ans = [0] * n
	dif = set()
	for i in range(n):
		for j in s:
			if (l[i][1], j + 1) not in d and j + 1 != l[i][1]:
				ans[j] = l[i][1]
				dif.add(j)
		s = s - dif
	print(' '.join((str(x) for x in ans)))
	print()


import sys
from collections import defaultdict
t = int(sys.stdin.readline())
while t:
	t -= 1
	n = int(sys.stdin.readline())
	d = [int(x) for x in sys.stdin.readline().split()]
	graph = defaultdict(set)
	for i in range(n - 1):
		(u, v) = [int(x) for x in sys.stdin.readline().split()]
		graph[d[u - 1]].add(d[v - 1])
		graph[d[v - 1]].add(d[u - 1])
		graph[d[u - 1]].add(d[u - 1])
		graph[d[v - 1]].add(d[v - 1])
	index = {d[i]: i + 1 for i in range(n)}
	max_val = d.copy()
	max_val.sort(reverse=True)
	ans = []
	for i in range(n):
		values = graph[d[i]]
		for m in max_val:
			if m not in values:
				ans.append(str(index[m]))
				break
	print(' '.join(ans))


import sys
from collections import defaultdict
from pprint import pprint

class graph:

	def __init__(self):
		self.d = defaultdict(list)

	def addedge(self, u, v):
		self.d[u].append(v)
		self.d[v].append(u)
t = int(sys.stdin.readline())

class population:

	def __init__(self, index, popu):
		self.index = index
		self.popu = popu

	def __eq__(self, other):
		return self.popu == other.popu

	def __hash__(self):
		return hash(self.index)
while t:
	n = int(sys.stdin.readline())
	population_list = [int(x) for x in sys.stdin.readline().split()]
	population_class_list = []
	for i in range(n):
		population_class_list.append(population(i, population_list[i]))
	population_class_list = sorted(population_class_list, key=lambda k: k.popu, reverse=True)
	g = graph()
	for i in range(n - 1):
		(u, v) = map(int, sys.stdin.readline().split())
		g.addedge(u - 1, v - 1)
	tmp_str = ''
	for i in range(n):
		removing_set = set()
		removing_set.add(i)
		try:
			g.d[i]
			removing_set = removing_set | set(g.d[i])
			for i in population_class_list:
				if i.index not in removing_set:
					if tmp_str == '':
						tmp_str = str(i.index + 1)
					else:
						tmp_str = tmp_str + ' ' + str(i.index + 1)
					break
		except KeyError:
			if tmp_str == '':
				tmp_str = str(i.index + 1)
			else:
				tmp_str = tmp_str + ' ' + str(i.index + 1)
			pass
	print(tmp_str)
	t = t - 1


def main(args):
	T = int(input())
	while T:
		T -= 1
		N = int(input())
		P = list(map(int, input().split()))
		k = 0
		p_map = {}
		for i in P:
			k += 1
			p_map[i] = k
		Q = list(P)
		Q.sort(reverse=True)
		citymap = [[P[i]] for i in range(N)]
		for i in range(N - 1):
			(a, b) = list(map(int, input().split()))
			citymap[a - 1].append(P[b - 1])
			citymap[b - 1].append(P[a - 1])
		for i in range(N):
			citymap[i].sort(reverse=True)
		for i in range(N):
			l = 0
			max = Q[0]
			for j in citymap[i]:
				if j >= max:
					l += 1
					max = Q[l]
			print(p_map[max], end=' ')
	return 0
import sys
sys.exit(main(sys.argv))


t = int(input())
for t0 in range(t):
	n = int(input())
	p = [int(i) for i in input().strip().split()]
	di2 = dict()
	for i in range(n):
		p[i] = [p[i], i + 1]
	dic = dict()
	for i in range(1, n + 1):
		dic[i] = [i]
	for i in range(n - 1):
		s = [int(i) for i in input().strip().split()]
		(a, b) = (s[0], s[1])
		dic[a].append(b)
		dic[b].append(a)
	p.insert(0, [0, 0])
	ans = []
	mx = 0
	srt = sorted(p, key=lambda x: x[0], reverse=True)
	for i in range(1, n + 1):
		mx = -1
		for k in srt:
			fl = 0
			for j in dic[i]:
				if p[j][0] == k[0]:
					fl = 1
					break
			if fl == 0:
				mx = k[1]
				break
		if mx == -1:
			ans.append(0)
		else:
			ans.append(mx)
	print(*ans)


from collections import defaultdict
t = int(input())
for _ in range(t):
	d = defaultdict(set)
	n = int(input())
	p = list(map(int, input().split()))
	for _ in range(n - 1):
		(x, y) = map(int, input().split())
		d[x].add(y)
		d[y].add(x)
	arr = [(value, index + 1) for (index, value) in enumerate(p)]
	arr.sort(reverse=True)
	ans = []
	for i in range(1, n + 1):
		s = d[i]
		flag = False
		for (value, index) in arr:
			if index not in s and index != i:
				ans.append(index)
				flag = True
				break
		if not flag:
			ans.append(0)
	print(*ans, sep=' ')


t = int(input())
while t > 0:
	n = int(input())
	adj_list = [{} for i in range(n)]
	pis = [(index, int(x)) for (index, x) in enumerate(input().strip().split())]
	for i in range(n - 1):
		(u, v) = [int(x) for x in input().strip().split()]
		adj_list[u - 1][v - 1] = True
		adj_list[v - 1][u - 1] = True
	answer_array = [0] * n
	pis.sort(key=lambda x: x[1], reverse=True)
	for i in range(n):
		for city in pis:
			pass
			if city[0] == i or city[0] in adj_list[i]:
				answer_array[i] += 1
			else:
				break
	for (i, val) in enumerate(answer_array):
		answer_array[i] = pis[val][0] + 1
	print(' '.join((str(x) for x in answer_array)))
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a1 = [(a[i], i + 1) for i in range(n)]
	a1.sort(key=lambda x: x[0])
	mm = {i + 1: set() for i in range(n)}
	for _ in range(n - 1):
		(x, y) = map(int, input().split())
		mm[x].add(y)
		mm[y].add(x)
	res = []
	for i in range(1, n + 1):
		flag = True
		for j in range(n, 0, -1):
			if a1[j - 1][1] not in mm[i] and i != a1[j - 1][1] and flag:
				res.append(a1[j - 1][1])
				flag = False
				break
		if flag:
			res.append(0)
	print(' '.join(map(str, res)))


from operator import itemgetter
t = int(input())
while t:
	t -= 1
	n = int(input())
	pi = [int(x) for x in input().split()]
	i = 1
	planet = []
	for x in pi:
		p = [i, x]
		i += 1
		planet.append(p)
	planets = sorted(planet, key=itemgetter(1))
	copy = sorted(planet, key=itemgetter(1))
	adjlist = []
	numneighpls = []
	for i in range(0, n):
		adjlist.append([])
		numneighpls.append(0)
	sortedlist = []
	i = 0
	while i < n - 1:
		ppair = [int(x) for x in input().split()]
		p1 = ppair[0]
		p2 = ppair[1]
		adjlist[p1 - 1].append(planet[p2 - 1][1])
		adjlist[p2 - 1].append(planet[p1 - 1][1])
		numneighpls[p1 - 1] += 1
		numneighpls[p2 - 1] += 1
		i += 1
	for i in range(0, n):
		adjlist[i].append(planet[i][1])
	for i in range(0, n):
		adjlist[i].sort()
		numneighpls[i] += 1
	for i in range(0, n):
		maxind = n - 1
		maxim = planets[maxind][1]
		j = numneighpls[i] - 1
		while 1:
			if maxim != adjlist[i][j]:
				print(planets[maxind][0], end=' ')
				break
			else:
				j -= 1
				maxind -= 1
				maxim = planets[maxind][1]


tc = int(input())
current = []
branch = {}
pop = []

def f(u, v):
	set(u, v)
	if pop[current[u]][0] == v:
		p = current[u]
		while p == 0 or not ifAvail(u, p):
			p = p - 1
		current[u] = p

def ifAvail(u, p):
	return not get(u, pop[p][0])

def get(u, v):
	if u == v:
		return True
	u = str(u)
	v = str(v)
	s = u + ' ' + v if u <= v else v + ' ' + u
	return s in branch

def set(u, v):
	u = str(u)
	v = str(v)
	branch[u + ' ' + v if u <= v else v + ' ' + u] = True
for t in range(tc):
	current = []
	branch = {}
	pop = []
	n = int(input())
	pop = input().split(' ')
	pop = [int(p) for p in pop]
	pop = [-1] + pop
	pop = sorted(enumerate(pop), key=lambda k: k[1])
	current = [n for x in range(n + 1)]
	current[pop[n][0]] = n - 1
	for x in range(n - 1):
		(u, v) = input().split(' ')
		u = int(u)
		v = int(v)
		f(u, v)
		f(v, u)
	print(*[pop[p][0] for p in current[1:]])


t = int(input())
for i in range(t):
	n = int(input())
	pop = list(map(int, input().split()))
	ind = []
	for i in range(len(pop)):
		ind.append((pop[i], i + 1))
	ind.sort(reverse=True)
	max_list = []
	for el in ind:
		max_list.append(el[1])
	adj = []
	for j in range(n):
		adj.append([j + 1])
	for j in range(n - 1):
		(a, b) = map(int, input().split())
		adj[a - 1].append(b)
		adj[b - 1].append(a)
	for k in range(n):
		j = -1
		while True:
			j += 1
			if max_list[j] not in adj[k]:
				break
		print(max_list[j], end=' ')


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	(brr, brray) = ({}, {})
	arr = list(map(int, input().split()))
	array = sorted(arr)
	for i in range(n):
		brr[arr[i]] = i
		brray[array[i]] = i
	graph = defaultdict(set)
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		graph[a - 1].add(b - 1)
		graph[b - 1].add(a - 1)
	for i in range(n):
		for j in range(n - 1, -1, -1):
			if brr[array[j]] not in graph[i] and i != brr[array[j]]:
				print(brr[array[j]] + 1, end=' ')
				break
		else:
			print(0, end=' ')


def diff(a, b):
	i = 0
	while i < len(a) and i < len(b) and (a[i] == b[i]):
		i += 1
	if i == len(b):
		return -1
	return b[i]
for _ in range(int(input())):
	n = int(input())
	pi = list(map(int, input().split()))
	temp = pi
	indexes = {-1: 0}
	for i in range(n):
		indexes[pi[i]] = i + 1
	pi = sorted(pi, reverse=True)
	adj_list = [[temp[x - 1]] for x in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj_list[u] += [temp[v - 1]]
		adj_list[v] += [temp[u - 1]]
	for i in range(1, n):
		adj_list[i] = sorted(adj_list[i], reverse=True)
		print(indexes[diff(adj_list[i], pi)], end=' ')
	adj_list[n] = sorted(adj_list[n], reverse=True)
	print(indexes[diff(adj_list[n], pi)])


import operator
i = int(input())
s = {}
for j in range(i):
	n = int(input())
	l = list(map(int, input().split()))
	d = dict(zip(range(1, n + 1), l))
	for k in range(n + 1):
		s[k] = set()
	for _ in range(n - 1):
		(a, b) = input().split()
		a = int(a)
		b = int(b)
		s[a].add(b)
		s[b].add(a)
	d = sorted(d.items(), key=operator.itemgetter(1))
	d.reverse()
	for i in range(1, n + 1):
		ans = 0
		for j in d:
			if j[0] not in s[i] and j[0] != i:
				ans = j[0]
				break
		print(ans, end=' ')
		ans = 0
	print()


from collections import defaultdict, OrderedDict
from operator import itemgetter

def binarySearch(arr, l, r, x):
	if r >= l:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return True
		elif arr[mid] > x:
			return binarySearch(arr, l, mid - 1, x)
		else:
			return binarySearch(arr, mid + 1, r, x)
	else:
		return False
for test in range(int(input())):
	n = int(input())
	pop = {}
	p = list(map(int, input().split()))
	j = 1
	for i in p:
		pop[i] = j
		j += 1
	t = -1
	lst = sorted(pop.keys())
	edg = defaultdict(list)
	j = 0
	for i in range(1, n):
		(a, b) = map(int, input().split())
		edg[a].append(b)
		edg[b].append(a)
	for i in range(1, n):
		edg[i].sort()
	for i in range(1, n + 1):
		t = -1
		while True:
			if binarySearch(edg[i], 0, len(edg[i]) - 1, pop[lst[t]]) == False and i != pop[lst[t]]:
				print(pop[lst[t]], end=' ')
				break
			elif len(edg[i]) == n - 1:
				print('0 ', end='')
				break
			t -= 1
	print('')


t = int(input())
for a0 in range(t):
	n = int(input())
	a = [int(i) for i in input().split(' ')]
	b = {}
	pop = {}
	for i in range(n):
		pop[a[i]] = i + 1
	a.sort()
	ind = []
	for i in a:
		ind.append(pop[i])
	for i in range(1, n + 1):
		b[i] = [i]
	for i in range(n - 1):
		(u, v) = input().split(' ')
		(u, v) = [int(u), int(v)]
		b[u].append(v)
		b[v].append(u)
	for i in b:
		temp = b[i]
		for i in range(n - 1, -1, -1):
			if ind[i] not in temp:
				print(ind[i], end=' ')
				break


t = int(input())
for _ in range(0, t):
	n = int(input())
	populations = list(map(int, input().split()))
	planets = []
	paths = {}
	for i in range(0, n):
		planet = (populations[i], i + 1)
		planets.append(planet)
		paths[i + 1] = [i + 1]
	for i in range(1, n):
		(a, b) = map(int, input().split())
		paths[a].append(b)
		paths[b].append(a)
	planets.sort(reverse=True)
	for i in range(1, n + 1):
		temp = list(paths[i])
		for i in range(0, n):
			if planets[i][1] not in temp:
				print(planets[i][1], end=' ')
				break


from collections import defaultdict
for test in range(int(input())):
	n = int(input())
	pop = {}
	p = list(map(int, input().split()))
	j = 1
	for i in p:
		pop[i] = j
		j += 1
	t = -1
	lst = sorted(pop.keys())
	edg = defaultdict(list)
	j = 0
	for i in range(1, n):
		(a, b) = map(int, input().split())
		edg[a].append(b)
		edg[b].append(a)
	for i in range(1, n + 1):
		t = -1
		while True:
			if pop[lst[t]] not in edg[i] and i != pop[lst[t]]:
				print(pop[lst[t]], end=' ')
				break
			elif len(edg[i]) == n - 1:
				print('0 ', end='')
			t -= 1
	print('')


t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	a = [[] for x in range(n + 3)]
	ip = []
	for m in range(n):
		ip.append([p[m], m + 1])
	ip.sort()
	ip.reverse()
	for j in range(n - 1):
		(x, y) = list(map(int, input().split()))
		a[x].append([p[y - 1], y])
		a[y].append([p[x - 1], x])
	for j in range(1, n + 1):
		a[j].append([p[j - 1], j])
		a[j].sort()
		a[j].reverse()
	for j in range(1, n + 1):
		temp = a[j]
		ind = 0
		for k in temp:
			if ip[ind][0] == k[0]:
				ind += 1
			else:
				break
		print(ip[ind][1] if ind < n - 1 else '0', end=' ')


T = int(input())
while T > 0:
	n = int(input())
	adj = list()
	p = list()
	b = input().split()
	for i in range(1, n + 1):
		adj.append([i])
		p.append([int(b[i - 1]), i])
	p.sort()
	pop = list()
	index = list()
	for i in range(0, n):
		pop.append(p[i][0])
		index.append(p[i][1])
	for i in range(1, n):
		a = input().split()
		adj[int(a[0]) - 1].append(int(a[1]))
		adj[int(a[1]) - 1].append(int(a[0]))
	mi = n - 1
	mc = n - 1
	m = index[mi]
	for i in adj:
		while index[mi] in i:
			if mi > 0:
				mi = mi - 1
				m = index[mi]
			else:
				m = 0
				break
		print(m, end=' ')
		mi = mc
		m = index[mi]
	T = T - 1
	print()


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	po = s.split()
	p = {}
	for j in range(n):
		p[int(po[j])] = j + 1
	k = list(p.keys())
	k.sort(reverse=True)
	tel = {}
	for j in range(n):
		tel[j + 1] = []
	for j in range(n - 1):
		b = input()
		c = b.split()
		tel[int(c[0])].append(int(c[1]))
		tel[int(c[1])].append(int(c[0]))
	for j in range(n):
		for l in range(n):
			if p[k[l]] in tel[j + 1]:
				continue
			elif p[k[l]] == j + 1:
				continue
			else:
				print(p[k[l]], end=' ')
				break


import numpy as np

def check(N, pop, teleports):
	pop_idx = np.argsort(pop)[::-1]
	pop_idx = [int(i + 1) for i in pop_idx]
	G = {}
	for i in range(1, N + 1):
		G[i] = [i]
	capitals = [(pop_idx[0], 0)] * N
	for (u, v) in teleports:
		G[u].append(v)
		G[v].append(u)
		if capitals[u - 1][0] == u or capitals[u - 1][0] == v:
			neighbors = G[u]
			changed = False
			for i in range(capitals[u - 1][1], N - 1):
				if pop_idx[i] not in neighbors:
					capitals[u - 1] = (pop_idx[i], i)
					changed = True
					break
			if not changed:
				capitals[u - 1] = (0, N - 1)
		if capitals[v - 1][0] == u or capitals[v - 1][0] == v:
			neighbors = G[v]
			changed = False
			for i in range(capitals[v - 1][1], N - 1):
				if pop_idx[i] not in neighbors:
					capitals[v - 1] = (pop_idx[i], i)
					changed = True
					break
			if not changed:
				capitals[v - 1] = (0, N - 1)
	return [str(capitals[i][0]) for i in range(len(capitals))]
T = int(input().strip())
for _ in range(T):
	N = int(input().strip())
	pop = list(map(int, input().strip().split()))
	teleports = [tuple(map(int, input().strip().split())) for _ in range(N - 1)]
	print(' '.join(check(N, pop, teleports)))


def solve(populations, links):
	cities = []
	for i in range(1, len(populations)):
		cities.append((i, populations[i]))
	cities.sort(key=lambda c: c[1], reverse=True)
	solution = []
	for i in range(1, len(links)):
		infected_cities = [(i, populations[i])]
		for k in links[i]:
			infected_cities.append((k, populations[k]))
		infected_cities.sort(key=lambda c: c[1], reverse=True)
		i1 = 0
		i2 = 0
		while i1 < len(cities) and i2 < len(infected_cities) and (cities[i1] == infected_cities[i2]):
			i1 += 1
			i2 += 1
		if i1 < len(cities):
			solution.append(cities[i1][0])
		else:
			solution.append(-1)
	return solution
T = int(input())
while T > 0:
	N = int(input())
	populations = [int(x) for x in input().split()]
	populations = [0] + populations
	links = [[] for x in range(1, N + 1)]
	links = [[]] + links
	for i in range(N - 1):
		(V, U) = [int(x) for x in input().split()]
		links[V].append(U)
		links[U].append(V)
	solution = solve(populations, links)
	for p in solution:
		print(p, end=' ')
	print('')
	T -= 1