問題文

遊園地「パ研ランド」には、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}) \]

楽しさの最大値を求めてください。

制約

• 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} \lt V_{i} \leq N (1 \leq i \leq M)
• i \neq j ならば、 (U_{i}, V_{i}) \neq (U_{j}, V_{j})
• 入力は全て整数

入力例 1

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

出力例 1

1.5

例えば、 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

4 2 
1 1 2 3 
1 2 
3 4 

出力例 2

0.5 

遊園地の地点の組であって、レールのみでは接続されていないようなものが存在する可能性もあります。