问题描述

给定一个包含 $N$ 个结点 $M$ 条边的无向图 $G$ ，结点编号 $1...N$ 。其中每个结点都有一个点权 $W_i$ 。

你可以从 $M$ 条边中任选恰好一条边删除，如果剩下的图恰好包含 $2$ 个连通分量，就称这是一种合法的删除方案。

对于一种合法的删除方案，我们假设 $2$ 个连通分量包含的点的权值之和分别为 $X$ 和 $Y$ ，请你找出一种使得 $X$ 与 $Y$ 的差值最小的方案。输出 $X$ 与 $Y$ 的差值。

输入格式

第一行包含两个整数 $N$ 和 $M$ 。

第二行包含 $N$ 个整数， $W_1,W_2,...W_N$ 。

以下 $M$ 行每行包含 $2$ 个整数 $U$ 和 $V$ ，代表结点 $U$ 和 $V$ 之间有一条边。

一个整数代表最小的差值。如果不存在合法的删除方案，输出 -1。

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

由于 1 和 2 之间实际有 $2$ 条边，所以合法的删除方案有 $2$ 种，分别是删除 $(2,3)$ 之间的边和删除 $(3,4)$ 之间的边。

删除 $(2,3)$ 之间的边，剩下的图包含 $2$ 个连通分量: $\{1,2\}$ 和 $\{3,4\}$ ，点权和分别是 $30$ 、 $70$ ，差为 $40$ 。

删除 $(3,4)$ 之间的边，剩下的图包含 $2$ 个连通分量: $\{1,2,3\}$ 和 $\{4\}$ ，点权和分别是 $60$ 、 $40$ ，差为 $20$ 。

对于 $20\%$ 的数据， $1≤N,M≤10000$ 。

对于另外 $20\%$ 的数据，每个结点的度数不超过 $2$ 。

对于 $100\%$ 的数据， $1≤N,M≤200000$ ， $0≤W_i≤10^9$ ， $1≤U,V≤N$ 。