Thành phố trọng yếu

Xem dạng PDF

Gửi bài giải


Điểm: 0,36 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Nguồn bài:
VNOI '10
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Đất nước Hạnh Phúc có ~N~ thành phố được nối với nhau bởi ~M~ đường nối hai chiều. Giữa hai thành phố bất kỳ chỉ có nhiều nhất một con đường.

Chính quyền nước này đưa ra một tiêu chí để đánh giá độ quan trọng của mỗi thành phố, theo đó độ quan trọng của một thành phố ~X~ được tính bằng số cặp thành phố ~A~ và ~B~ mà để di chuyển từ ~A~ đến ~B~ (và ngược lại) bắt buộc phải đi qua thành phố ~X~.

Bạn hãy lập trình tính độ quan trọng trung bình của tất cả các thành phố.

Input

Dòng đầu tiên chứa hai số nguyên ~N, M~ ~(1 \le N \le 20000, 0 \le M \le 200000)~.

~M~ dòng tiếp theo mỗi dòng chứa ~2~ số nguyên ~u, v~ ~(1 \le u, v \le N)~ mô tả một đường nối.

Output

Gồm một số thực duy nhất là độ quan trọng trung bình của các thành phố. Kết quả được tính là đúng nếu chênh lệch với đáp án không quá ~10^{-2}~

Sample Input

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

Sample Output

1.400000000

Note

image

Giải thích: Độ quan trọng của các thành phố ~1, 2, 3, 4, 5~ lần lượt là ~0, 3, 4, 0, 0~. Độ quan trọng của thành phố ~3~ là ~4~ vì có ~4~ cặp thành phố mà khi di chuyển đến nhau cần đi qua thành phố ~3~: ~(1, 4), (1, 5), (2, 4), (2, 5)~.


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    minzdapoet1102  đã bình luận lúc 25, Tháng 2, 2024, 8:27

    Mình có thắc mắc: theo đề cho thì "giữa hai thành phố bất kì chỉ có nhiều nhất một con đường". Nhưng trong test ví dụ(hình vẽ bên trên) thì từ 3 đi đến 5 có 2 đường đi: 3->5 và 3->4->5. ??


    • 1
      Ceaturs  đã bình luận lúc 4, Tháng 3, 2024, 14:08

      ý là nó bảo cạnh á bạn, giữa 2 đỉnh chỉ có 1 cạnh.