Tango islands are group of N islands having large amount of trees of mango.All those islands are connected by N-1 bridges in such a way that it is possible to travel between any two island using these bridges. But this morning there is a news that a pirate ship is going to attack on the islands to steal mangoes.And it is known that if there is a attack on a specific island then all the islands directly connected to it and the island itself would get destroyed and all mangoes will be stolen.

Islands are numbered from 1 to N. And the number of mangoes in them be M1,M2, ....., MN respectively.It is also known that all Mi are distinct.

Let the pirates attack at island V.So in this case all the islands directly connected to this island will be destroyed. After the attack a fruit-protection committee is formed to protect fruits from further attacks. but due to limited resources you can protect only one island. Now you will have to set a protection on a island(out of remaining islands) with max number of fruits. you will have to find the island with max number of fruits (out of remaining islands).

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 M1, M2, ..., MN denoting the number of mangoes in island.

Next N-1 lines contain two space-separated integers each C and D denoting that there is a bridge between C and D.

Output:

For each test case, output a single line containing N integers A1, A2, ..., AN separated by a space. Here Ai denotes the number of the island picked to transport the fruits incase the attack is on island i. In case V is connected to all the islands output 0.

Constraints:

1 ≤ T ≤ 5
1 ≤ N ≤ 50000
1 ≤ Mi ≤ 10^6
All Mi are distinct
1 ≤ C ≤ N
1 ≤ D ≤ N