Problem Description

Given an undirected graph $G$ with $N$ nodes and $M$ edges, where the nodes are numbered $1 \cdots N$. Each node has a weight $W_i$.

You may choose exactly one edge from the $M$ edges and delete it. If the remaining graph contains exactly $2$ connected components, then this is called a valid deletion plan.

For a valid deletion plan, suppose the sums of node weights in the two connected components are $X$ and $Y$, respectively. Please find a plan that makes the difference between $X$ and $Y$ as small as possible, and output the difference between $X$ and $Y$.

Input Format

The first line contains two integers $N$ and $M$.

The second line contains $N$ integers $W_1, W_2, \cdots, W_N$.

The following $M$ lines each contain two integers $U$ and $V$, indicating that there is an edge between node $U$ and node $V$.

Output Format

Output one integer representing the minimum difference. If there is no valid deletion plan, output $-1$.

4 4
10 20 30 40
1 2
2 1
2 3
4 3

20

Hint

Sample Explanation

Since there are actually $2$ edges between $1$ and $2$, there are $2$ valid deletion plans: deleting the edge between $(2, 3)$ and deleting the edge between $(3, 4)$.

If we delete the edge between $(2, 3)$, the remaining graph contains $2$ connected components: $\{1,2\}$ and $\{3,4\}$. Their weight sums are $30$ and $70$, and the difference is $40$.

If we delete the edge between $(3, 4)$, the remaining graph contains $2$ connected components: $\{1,2,3\}$ and $\{4\}$. Their weight sums are $60$ and $40$, and the difference is $20$.

Constraints and Notes for Test Cases

• For $20\%$ of the testdata, $1 \le N, M \le 10000$.
• For another $20\%$ of the testdata, the degree of each node is at most $2$.
• For $100\%$ of the testdata, $1 \le N, M \le 200000$, $0 \le W_i \le 10^9$, $1 \le U, V \le N$.

The 14th Lanqiao Cup Software Contest Finals, C/C++ College Group B, Problem F.

Translated by ChatGPT 5