删除顶点 2

题目描述

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

你将重复以下操作 $N$ 次：

选择一个尚未被删除的顶点 $x$，删除顶点 $x$ 以及所有与顶点 $x$ 关联的边。本次操作的代价为：与顶点 $x$ 通过一条边直接相连、且尚未被删除的顶点上整数之和。

将整个 $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

数据范围

• $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$
• 给定图是简单图
• 输入中的所有值均为整数