Maximum Difference in Tree Nodes

You are given a tree with N nodes. Each node has an integer value. The tree is represented using N-1 edges such that it forms a connected acyclic graph. Your task is to calculate the maximum difference between the values of any two nodes in the tree. Essentially, this is the difference between the maximum and minimum values.

In mathematical terms, if the set of node values is \(\{a_1, a_2, \dots, a_N\}\), then the answer is:

[ \max_{1 \le i \le N}(a_i) - \min_{1 \le i \le N}(a_i). ]

It is guaranteed that the input corresponds to one or more valid trees.

inputFormat

The first line contains an integer (T) denoting the number of test cases. For each test case, the first line contains an integer (N) representing the number of nodes in the tree. The second line contains (N) space-separated integers, where the (i^{th}) integer represents the value of the (i^{th}) node. Each of the next (N-1) lines contains two space-separated integers (u) and (v) that denote an undirected edge between nodes (u) and (v).

outputFormat

For each test case, output a single integer in a separate line denoting the maximum difference between the values of any two nodes in the tree.## sample

2
5
3 1 4 10 6
1 2
1 3
3 4
3 5
3
7 8 3
1 2
1 3

9
5