EIU Programming Practices and Exams

Ngân và nhóm bạn của mình vừa có kết quả thi tốt nghiệp THPT xong. Để chứng minh rằng nhóm mình có học lực tốt, Ngân muốn biết điểm trung bình của nhóm Ngân so với nhóm khác như thế nào. Mỗi nhóm là tập hợp những người bạn (bạn trực tiếp hoặc thông qua một số người khác).

Input

Dòng đầu tiên gồm số 2 số nguyên n, m là số người và số mối quan hệ bạn bè. (0 ≤ n, m ≤ 2 * 10⁵). Mỗi người được đánh số từ 0 đến n – 1.

Số thực thứ i trong dòng tiếp thể hiện điểm thi tốt nghiệp của người thứ i.

M dòng tiếp theo, mỗi dòng là 2 số u và v, thể hiện bạn u và v là bạn bè của nhau.

Output

Với mỗi nhóm, xuất ra người đại diện (có thứ tự nhỏ nhất trong nhóm) và điểm trung bình của nhóm. Các nhóm được sắp xếp theo thứ tự điểm trung bình giảm dần (khi chưa làm tròn), người đại diện tăng dần. Điểm trung bình được làm tròn một chữ số thập phân..

Example

Input:
5 4
9.2 8.3 8.4 5.6 7.2
1 2 
2 4
4 1
0 3

Output:
1 8.0
0 7.4