Vườn Thú Của Bé

Một vườn thú có $n$ khu, đánh số từ $1$ đến $n$. Khu thứ $i$ chứa $a_i$ con thú. Có $m$ con đường, mỗi con đường nối hai khu khác nhau. Vườn thú liên thông: từ một khu bất kỳ luôn đi được tới mọi khu khác qua các con đường.

Với hai khu $p$ và $q$ ($p\ne q$), xét mọi đường đi đơn từ $p$ đến $q$. Với mỗi đường đi, ghi lại số nhỏ nhất trong số lượng thú của các khu nằm trên đường đi đó. Gọi $f(p,q)$ là giá trị lớn nhất trong các số đã ghi (tức là giá trị lớn nhất có thể của "khu ít thú nhất trên đường đi", lấy trên tất cả các đường đi từ $p$ tới $q$).

Hãy tính giá trị trung bình của $f(p,q)$ trên tất cả các cặp có thứ tự $(p,q)$ với $p\ne q$. Có tất cả $n(n-1)$ cặp như vậy.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i$ và $y_i$, mô tả con đường nối khu $x_i$ và khu $y_i$.

Các con đường là hai chiều, mỗi cặp khu được nối bởi tối đa một con đường.

Dữ liệu ra

Ghi ra một số thực: giá trị trung bình cần tìm. Đáp án được chấp nhận nếu sai số tương đối hoặc tuyệt đối không vượt quá ${10}^{-4}$.

Ràng buộc

• $2\le n\le {10}^5$
• $0\le m\le {10}^5$
• $0\le a_i\le {10}^5$
• $1\le x_i,y_i\le n$, $x_i\ne y_i$

Ví dụ