Minimum Difference in Component Weights After Deleting an Edge

You are given an undirected graph \(G\) with \(N\) nodes and \(M\) edges. The nodes are numbered from \(1\) to \(N\) and each node \(i\) has a weight \(W_i\). You are allowed to delete exactly one edge from the given \(M\) edges. A deletion is considered valid if, after the deletion, the remaining graph consists of exactly two connected components.

For each valid deletion, let the sums of the weights of nodes in the two connected components be \(X\) and \(Y\) respectively. Your task is to find a deletion which minimizes \(|X - Y|\) and output this minimum absolute difference.

Note: An edge removal only results in two connected components if the removed edge is a bridge (i.e. its removal disconnects the graph).

The mathematical formulation of the condition is as follows:

[ \text{Minimize } |X - Y|, \quad \text{where } X + Y = \sum_{i=1}^{N} W_i \text{ and the deletion yields exactly two connected components.} ]

inputFormat

The first line contains two integers \(N\) and \(M\), representing the number of nodes and edges respectively.

The second line contains \(N\) integers, \(W_1, W_2, \ldots, W_N\), where \(W_i\) is the weight of node \(i\).

The following \(M\) lines each contain two integers \(u\) and \(v\), representing an undirected edge connecting node \(u\) and node \(v\).

outputFormat

Output a single integer representing the minimum absolute difference \(|X - Y|\) between the sums of the weights of the nodes in the two connected components after a valid deletion.

sample

4 4
1 2 3 4
1 2
2 3
2 4
3 4

8