There is an undirected tree where each vertex is numbered from $1$ to n$,$ and each contains a data value. The sum of a tree is the sum of all its nodes$$ data values. If an edge is cut, two smaller trees are formed. The difference between two trees is the absolute value of the difference in their sums.

Given a tree, determine which edge to cut so that the resulting trees have a minimal difference between them, then return that difference.

Example

data $=[1,2,3,4,5,6]$

edges $=[(1,2),(1,3),(2,6),(3,4),(3,5)]$

In this case, node numbers match their weights for convenience. The graph is shown below.

The values are calculated as follows:

Edge Tree $1$ Tree $2$ Absolute

Cut Sum Sum Difference

$18135$

$29123$

$36159$

$441713$

$551611$

The minimum absolute difference is $3.$

Note: The given tree is always rooted at vertex $1.$