AT_pakencamp_2024_day3_2_e Roller Coaster

游乐园“パ研ランド”中有 $N$ 个地点，第 $i$ 个地点的高度为 $H_i$。园内有 $M$ 条供过山车使用的双向轨道，第 $i$ 条轨道连接点 $U_i$ 与 $V_i$。 你想使用这些轨道中的若干条，构造满足以下条件的过山车路线： - 经过的地点顺序记为 $v_0, v_1, \dots, v_n$，必须满足 $v_0 = v_n$。 - 对于所有 $i$（$1 \leq i \leq n$），$v_{i-1}$ 和 $v_i$ 之间存在直接连接的轨道。 此外，过山车的**乐趣值**定义如下： \[ \frac{1}{n} \sum_{i=1}^n \max(0, H_{v_{i-1}} - H_{v_i}) \] 请你求出乐趣值的最大值。

输入通过标准输入按以下格式给出。 > $N$ $M$ > $H_1$ $H_2$ $\ldots$ $H_N$ > $U_1$ $V_1$ > $U_2$ $V_2$ > $\vdots$ > $U_M$ $V_M$

输出答案。只要你的答案与真值的绝对误差或相对误差不超过 $10^{-9}$，即可判为正确。

### 样例解释 1 例如，按照 $4, 3, 2, 1, 4$ 的顺序经过的过山车路线满足题目条件。其乐趣值为： - $H_4 - H_3 = 1$ - $H_3 - H_2 = 1$ - $H_2 - H_1 = 1$ - $H_1 - H_4 = -3$ 所以乐趣值为 $(\max(0, 1) + \max(0, 1) + \max(0, 1) + \max(0, -3))/4 = 0.75$。 不过，若构造乐趣值最大的路径，该值可以达到 $1.5$。 ### 样例解释 2 游乐园中有些点的组合可能仅靠轨道并不连通。 ### 数据范围 - $2 \leq N \leq 2 \times 10^5$ - $1 \leq M \leq 2 \times 10^5$ - $1 \leq H_i \leq 10^9$（$1 \leq i \leq N$） - $1 \leq U_{i} < V_{i} \leq N$（$1 \leq i \leq M$） - 若 $i \neq j$，则 $(U_i, V_i) \neq (U_j, V_j)$ - 所有输入均为整数。 由 ChatGPT 5 翻译