Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TQ_KT1B3 - TAX

* Các bạn HS chú ý: Khi nộp bài máy chấm chỉ chấm test ví dụ của đề bài, sau khi kết thúc 
bài KT chúng tôi sẽ chấm lại
với bộ test đầy đủ, vì vậy hãy test kỹ trước khi nộp bài mình.

Nước Flantland có hai tập đoàn kinh tế lớn Y và G chi phối toàn bộ hoạt động thương mại trong cả nước.
Flantland có n thành phố, đánh số từ 1 đến n (3<=n<=1000). Các thành phố này được nối với nhau bởi
hệ thống giao thông gồm m đường (n-1<=m<=5000), mỗi đường nối một cặp thành phố và là đường hai 
chiều, đảm bảo có đường đi lại giữa hai thành phố bất kỳ trong nước (trực tiếp hoặc đi qua một số thành 
phố khác). Giữa hai thành phố bất kỳ có không quá một đường nối trực tiếp. 

Các thành phố chi phối bởi công ty Y được gọi là những thành phố vàng, các thành phố còn lại bị chi phối
bởi công ty G được gọi là thành phố xanh. Việc mua bán chỉ được tiến hành giữa các thành phố cùng màu.
Khi vận chuyển hàng hóa, chủ hàng phải trả thuế 1 flat (đơn vị tiền tệ của nước Flatland) trên mỗi đường
đi, ngoài ra, khi đi qua thành phố khác màu với thành phố xuất phát, chủ hàng còn phải trả thêm 3 flat.
Dĩ nhiên, khi vận chuyển hàng hóa, chủ hàng bao giờ cũng chọn con đường ứng với thuế phải trả nhỏ nhất.

Yêu cầu: Cho biết n, m và mạng giao thông trong Flatland. Hãy tính thuế trung bình T phải trả khi vận
chuyển hàng giữa hai thành phố cùng màu.

Input

  • Dòng đầu tiên chứa hai số nguyên n, m.
  • Dòng hai chứa n kí tự, mỗi kí tự là Y hoặc G là màu của các thành phố tương ứng.
  • m dòng sau:Mỗi dòng chứa hai số nguyên i, j xác định đường nỗi từ i đến j

Output

  • Gồm một dòng chứa số thực T (lấy 10 chữ số phần thập phân)

Example

Input:

5  5

YYGYG

1    2

5    1

3    4

3    2

5    4 Output: 4.0000000000

Ràng buộc: 50% điểm, tương ứng với 50% bộ test có n <= 100, m <= 500.

* Giải thích test ví dụ:

- Có 5 thành phố, các thành phố 1, 2, 4 màu vàng và 3, 5 màu xanh.

- Có 4 cặp thành phố cùng màu là (1,2), (1,4), (2,4) và (3,5), đường đi bị nộp ít thuế nhất giữa các cặp thành
phố này như sau:

            + 1 -> 2: Thuế = 1

            + 1 -> 5 -> 4: Thuế = 1 + 3 + 1 = 5

            + 2 -> 3 -> 4: Thuế = 1 + 3 + 1 = 5

            + 3 -> 4 -> 5: Thuế = 1 + 3 + 1 = 5

=> Thuế trung bình phải nộp là: (1 + 5 + 5 + 5) /4 = 4.0000000000


Được gửi lên bởi:Vương Trung Hiếu Nghĩa
Ngày:2014-08-20
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG JAVA PAS-GPC PAS-FPC
Nguồn bài:Thầy Hòa - Tuyên Quang

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.