Dane jest drzewo o $N$ wierzchołkach. Wierzchołki drzewa są ponumerowane od $1$ do $N$, a na każdym z nich zapisana jest jedna z liter U, C lub P. Znajdź liczbę par $(a, b)$ spełniających poniższy warunek ($1 \le a < b \le N$):

• Po zebraniu liter ze wszystkich wierzchołków należących do prostej ścieżki od wierzchołka $a$ do wierzchołka $b$ i ich ponownym uporządkowaniu, można utworzyć słowo postaci $\text{(UCPC)}^k$ ($k \ge 1$).

Wejście

W pierwszym wierszu podana jest liczba wierzchołków $N$ ($1 \le N \le 200\,000$).

W kolejnym wierszu podany jest ciąg znaków $S$ o długości $N$, składający się wyłącznie z liter U, C i P.

W kolejnych $N - 1$ wierszach podane są po dwie liczby całkowite $u_i$ oraz $v_i$, oddzielone spacją. Oznacza to, że wierzchołek $u_i$ i wierzchołek $v_i$ są bezpośrednio połączone krawędzią w drzewie ($1 \le u_i, v_i \le N$, $u_i \neq v_i$).

Wyjście

Wypisz liczbę par $(a, b)$ spełniających podany warunek.

Przykład

Wejście 1

5
UCCPP
2 3
4 3
3 5
2 1

Wyjście 1

2

Wejście 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

Wyjście 2

3

Uwagi

Drzewo odpowiadające pierwszemu przykładowi wygląda następująco:

Rysunek J.1: Drzewo odpowiadające pierwszemu przykładowi

Korzystając ze ścieżki między wierzchołkiem 1 a wierzchołkiem 4 oraz między wierzchołkiem 1 a wierzchołkiem 5, można utworzyć słowo postaci $\text{(UCPC)}^k$ dla $k = 1$.

W przypadku drugiego przykładu można utworzyć 2 słowa postaci (UCPC) dla $k = 1$ oraz 1 słowo postaci (UCPCUCPC) dla $k = 2$.