Cut The Tree

Problem Description

Alice and Bob are playing the game "Cut The Tree" on a tree $T$ with $n$ nodes indexed from $1$ to $n$. For each node $u$ , there is a mysterious weights $w_u$ on it. The game will be played in the following order:

1. Alice choose an edge of the tree and cut it. So the tree $T$ will be divided into two new trees $T_1,T_2$ .
2. Bob selects one of the two trees to take away, and gives the other to Alice.
3. Bob selects two nodes $u,v$ from his tree ( $u=v$ is allowed), and his score is $w_u\oplus w_v$ , where $\oplus$ means bitwise XOR. And so for Alice, she selects two nodes $u',v'$ from her own tree ( $u'=v'$ is allowed), and her score is $w_{u'}\oplus w_{v'}$ . The final score of the game is Bob's score minus Alice's score. Bob wants to maximize it, while Alice wants to minimize it. If both of them is clever enough, what's the final score of the game?

Input

The first line of the input contains an integer $T\ (1\le T\le 5)$, indicating the number of the test cases. For each test case: The first line contains a single integer $n\ (2\le n\le 2\times 10^5)$, indicating the number of the nodes of the tree. The second line contains $n$ integers $w_1,w_2\dots,w_n\ (0\le w_i\le 10^9)$, indicating the weight of the nodes. Then the following $n-1$ lines, each line contains two integers $u_i,v_i\ (1\le u_i,v_i\le n, u_i\not =v_i)$ , indicating an undirected edge of the tree. It's guaranteed that the graph is a tree.

Output

For each test case, print one line contains a single integer, indicating the final score of the game.

Sample Input

2
5
1 2 3 4 5
1 2
2 3
3 4
4 5
9
4 52 32 34 65 57 26 18 12
2 1
3 1
4 3
5 1
6 5
7 4
8 7
9 7

Sample Output

2
62

Hint

For the first sample, Alice will choose to cut the edge connected $3$ and $4$, then Bob's score will be $3$ and Alice's score will be $1$.

Source

2023“钉耙编程”中国大学生算法设计超级联赛（5）