The Game (Easy Version)
Contest: Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2)
Difficulty rating: 2000
Tags: data structures, dfs and similar, games, graphs, greedy, trees

This is the easy version of the problem. The difference between the versions is that in this version, you only need to find one of the possible nodes Cirno may choose. You can hack only if you solved all versions of this problem.

Cirno and Daiyousei are playing a game with a tree$$$^{\text{∗}}$$$ of $$$n$$$ nodes, rooted at node $$$1$$$. The value of the $$$i$$$-th node is $$$w_i$$$. They take turns to play the game; Cirno goes first.

In each turn, assuming the opponent chooses $$$j$$$ in the last turn, the player can choose any remaining node $$$i$$$ satisfying $$$w_i>w_j$$$ and delete the subtree$$$^{\text{†}}$$$ of node $$$i$$$. In particular, Cirno can choose any node and delete its subtree in the first turn.

The first player who can not operate wins, and they all hope to win. Find one of the possible nodes Cirno may choose so that she wins if both of them play optimally.

Input format:
The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of input test cases.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 4\cdot 10^5$$$) — the number of nodes in the tree.

The second line contains $$$n$$$ integers $$$w_1,w_2,\ldots,w_n$$$ ($$$1 \le w_i \le n$$$) — the value of each node.

The next $$$n-1$$$ lines contain the edges of the tree. The $$$i$$$-th line contains two integers $$$u_i,v_i$$$ ($$$1\le u_i,v_i \le n$$$, $$$u_i \neq v_i$$$) — an edge connecting $$$u_i$$$ and $$$v_i$$$. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$4\cdot 10^5$$$.

Output format:
For each test case, print one line.

If Cirno wins the game, print any possible node she may choose in the first turn.

Otherwise, print "0" (without quotes).

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first test case:

1. If Cirno chooses $$$1$$$ or $$$3$$$ in the first turn, Daiyousei cannot make a move, so Daiyousei wins.
2. If Cirno chooses $$$2$$$ or $$$4$$$ in the first turn, Daiyousei can only choose $$$3$$$, but after it Cirno cannot make a move, so Cirno wins.

Therefore, all possible nodes Cirno may choose are $$$2$$$ and $$$4$$$.

In the second test case, regardless of which node Cirno chooses, Daiyousei cannot make a move, so Daiyousei wins.

In the third and fourth test case, the only possible node Cirno may choose in the first turn is $$$2$$$.

In the fifth test case, all possible nodes Cirno may choose in the first turn are $$$3,4,6,7$$$ and $$$10$$$.

Example input:
5
4
2 2 4 3
1 2
1 3
2 4
5
1 2 3 4 5
1 2
2 3
3 4
4 5
3
1 2 3
1 2
1 3
5
3 1 3 4 5
1 2
2 3
3 4
4 5
10
1 2 3 2 4 3 3 4 4 3
1 4
4 6
7 4
6 9
6 5
7 8
1 2
2 3
2 10

Example output:
2
0
2
2
10

Editorial:
In the first round, the node $$$u$$$ chosen by Cirno must satisfy: there exists a node $$$v$$$ outside the subtree of $$$u$$$ such that $$$w_v > w_u$$$. If no such node exists, then Cirno will lose.
Among these nodes, Cirno can choose the node with the largest $$$w_u$$$. After this, Daiyousei can only select nodes that do not satisfy the above condition, and subsequently, Cirno will inevitably have no nodes left to operate on.
To determine whether there exists a node $$$v$$$ outside the subtree of $$$u$$$ such that $$$w_v > w_u$$$, we record the timestamp $$$dfn_u$$$ when each node is first visited during the DFS traversal of the tree, as well as the timestamp $$$low_u$$$ when the traversal of its subtree is completed. Since the timestamps outside the subtree form two intervals, namely $$$[1, dfn_u)$$$ and $$$(low_u, n]$$$, we need to check whether $$$\max(\max\limits_{dfn_v\in [1,dfn_u)}w_v,\max\limits_{dfn_v\in (low_u,n]}w_v)>w_u$$$ holds. This can be achieved by maintaining the maximum values in the prefix and suffix.
Additionally, we can enumerate the nodes in descending order of $$$w_i$$$ and maintain their lowest common ancestor (LCA). If the LCA of all $$$v$$$ satisfying $$$w_v > w_u$$$ is not a descendant of $$$u$$$, then there must exist a node $$$v$$$ outside the subtree of $$$u$$$ that satisfies $$$w_v > w_u$$$.
We can also enumerate the nodes in descending order of $$$w_i$$$ and maintain their minimum and maximum $$$dfn_i$$$, namely $$$mn,mx$$$. According to the conclusion above, we can check whether $$$mn<dfn_u$$$ or $$$mx>low_u$$$ holds. If either condition holds, then there must exist a node $$$v$$$ outside the subtree of $$$u$$$ that satisfies $$$w_v > w_u$$$.