You are given N nodes. There are N -1 connecting edges between any two nodes Each node has a value denoted by an array A

Write a program to divide the tree along an edge i so as to minimize the difference between the sums of the node values on either side of the element

Example

Consider N=3 ,edges-(1-2),(2-3) and A-10, 5, 20 You must determine the edge to be deleted that meets the following

conditions

If you delete the 1st edge 1-2 then the sum of difference would be abs(10-25) = 15.

If you delete the 2nd edge 2-3, then the sum of difference would be abs(15-20) = 5

Thus the minimum value is 5 when you delete the 2nd edge which is 2-3 Hence the answer is 5

Constraints

1 ≤ T ≤ 10

2≤ N ≤ 10^5

1 ≤ Ai ≤ 10^5

1≤ Ui, Vi ≤ N