THPT Chuyên Bến Tre

* 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