Cho một cây gồm $N$ đỉnh. Các đỉnh của cây được đánh số từ $1$ đến $N$, và mỗi đỉnh được viết một trong các chữ cái U, C, P. Hãy tìm số lượng cặp $(a, b)$ thỏa mãn điều kiện sau ($1 \le a < b \le N$):

• Thu thập tất cả các chữ cái được viết trên các đỉnh nằm trên đường đi đơn từ đỉnh $a$ đến đỉnh $b$, sau đó sắp xếp lại chúng để có thể tạo thành một chuỗi có dạng $(\text{UCPC})^k$ ($k \ge 1$).

Dữ liệu vào

Dòng đầu tiên chứa số lượng đỉnh $N$ ($1 \le N \le 200\,000$).

Dòng tiếp theo chứa một chuỗi $S$ có độ dài $N$ chỉ gồm các chữ cái U, C, P. Ký tự thứ $i$ của chuỗi $S$ thể hiện chữ cái được viết trên đỉnh $i$.

Trong $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i$ và $v_i$ cách nhau bởi khoảng trắng. Điều này có nghĩa là có một cạnh nối trực tiếp giữa đỉnh $u_i$ và đỉnh $v_i$ trên cây ($1 \le u_i, v_i \le N, u_i \ne v_i$).

Dữ liệu ra

In ra số lượng cặp $(a, b)$ thỏa mãn điều kiện.

Ví dụ

Dữ liệu vào 1

5
UCCPP
2 3
4 3
3 5
2 1

Dữ liệu ra 1

2

Dữ liệu vào 2

13
CUUUCCCCPCCPP
1 2
2 3
4 7
3 10
6 2
7 6
12 13
9 7
7 8
11 12
7 11
5 7

Dữ liệu ra 2

3

Ghi chú

Cây tương ứng với Ví dụ 1 được mô tả như hình dưới đây:

Hình J.1: Cây tương ứng với Ví dụ 1

Nếu sử dụng đường đi giữa đỉnh 1 và đỉnh 4, hoặc đường đi giữa đỉnh 1 và đỉnh 5, ta có thể tạo ra chuỗi dạng $(\text{UCPC})^k$ với $k = 1$.

Trong trường hợp của Ví dụ 2, ta có thể tạo ra 2 chuỗi dạng $(\text{UCPC})^k$ với $k = 1$, và 1 chuỗi dạng $(\text{UCPCUCPC})$ với $k = 2$.