当前没有测试数据。

E - 消除顶点 2

得分：500分

问题描述

给定一个具有$N$个顶点和$M$条边的简单无向图。第$i$条边连接顶点$U_i$和$V_i$。第$i$个顶点上有正整数$A_i$。

您将重复执行以下操作$N$次：

• 选择一个尚未删除的顶点$x$，然后删除顶点$x$和所有与顶点$x$相邻的边。此操作的成本是与顶点$x$通过边直接连接的未删除顶点上的整数之和。

我们将整个$N$次操作的成本定义为各个操作的成本的最大值。找出整个操作的最小可能成本。

约束

• $1 \le N \le 2 \times 10^5$
• $0 \le M \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• $1 \le U_i,V_i \le N$
• 给定的图是简单的（即没有自环和平行边）。
• 输入的所有值都是整数。

输入

输入从标准输入中按以下格式给出：

$N$ $M$

$A_1$ $A_2$ $\dots$ $A_N$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_M$ $V_M$

输出

输出答案。

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

3

通过以下操作，$N$次操作的最大成本可以是$3$。

• 选择顶点$3$。成本是$A_1=3$。
• 选择顶点$1$。成本是$A_2+A_4=3$。
• 选择顶点$2$。成本是$0$。
• 选择顶点$4$。成本是$0$。

$N$次操作的最大成本不能是$2$或更小，因此答案是$3$。

7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7

1199