Vận chuyển hàng

Đất nước Alpha có $n$ thành phố, được đánh số từ $1$ đến $n$. Các thành phố được nối với nhau bởi hệ thống giao thông gồm $m$ đường hai chiều, mỗi đường nối một cặp thành phố. Hệ thống giao thông đảm bảo có đường đi giữa hai thành phố bất kỳ trong nước, trực tiếp hoặc 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ó hai tập đoàn kinh tế lớn G và Y chi phối toàn bộ hoạt động thương mại trong cả nước. Mỗi thành phố thuộc một trong hai tập đoàn G hoặc Y. Khi vận chuyển hàng hóa từ thành phố này đến thành phố khác, chủ hàng phải trả chi phí $1$ AL (đơn vị tiền tệ nước Alpha) trên mỗi đường đi qua. Ngoài ra, mỗi khi đi qua một thành phố do tập đoàn khác quản lý, chủ hàng phải trả thêm $3$ AL. Chủ hàng luôn chọn đường đi có tổng chi phí nhỏ nhất.

Hai tập đoàn chỉ vận chuyển hàng giữa các thành phố của mình, nên thành phố xuất phát và thành phố đích luôn cùng tập đoàn; khoản $3$ AL tính cho mỗi thành phố trung gian trên đường đi thuộc tập đoàn còn lại (đi qua nhiều thành phố như vậy thì trả cho từng thành phố). Chi phí vận chuyển giữa hai thành phố $u$ và $v$ của cùng một tập đoàn là tổng chi phí nhỏ nhất của một đường đi từ $u$ đến $v$; mỗi cặp không thứ tự $\{u,v\}$ được tính một lần.

Yêu cầu: Cho biết $n,m$ và mạng giao thông trong Alpha. Hãy giúp hai tập đoàn G và Y tính tổng chi phí vận chuyển hàng giữa mọi cặp thành phố thuộc tập đoàn của họ.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n,m$.
• Dòng thứ hai chứa một xâu gồm $n$ ký tự, mỗi ký tự là G hoặc Y. Ký tự thứ $i$ cho biết thành phố $i$ thuộc tập đoàn G hay Y.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $i,j$ ($1\le i,j\le n$, $i\ne j$) xác định một đường nối thành phố $i$ với thành phố $j$.

Dữ liệu ra

In ra một dòng chứa hai số, lần lượt là tổng chi phí vận chuyển hàng giữa mọi cặp thành phố thuộc tập đoàn G và tổng chi phí vận chuyển hàng giữa mọi cặp thành phố thuộc tập đoàn Y. Nếu một tập đoàn có ít hơn hai thành phố thì tổng tương ứng bằng $0$.

Ràng buộc

• $1\le n\le 1000$, $n-1\le m\le 5000$.
• Mạng giao thông liên thông, không có hai đường nối cùng một cặp thành phố.

Subtasks

• Subtask 1: $n\le 100$, $m\le 5000$.
• Subtask 2: $n\le 1000$, $m\le 5000$.

Ví dụ