Un arbre à $N$ sommets est donné. Chaque sommet de l'arbre est numéroté de 1 à $N$, et porte l'une des lettres U, C ou P. Trouvez le nombre de paires $(a, b)$ satisfaisant la condition suivante : ($1 \le a < b \le N$)

• En collectant toutes les lettres écrites sur les sommets inclus dans le chemin simple reliant le sommet $a$ au sommet $b$ et en les réarrangeant, il est possible de former une chaîne de caractères de la forme (UCPC)$^k$. ($k \ge 1$)

Entrée

La première ligne contient le nombre de sommets $N$. ($1 \le N \le 200\,000$)

La ligne suivante contient une chaîne de caractères $S$ de longueur $N$, composée uniquement des lettres U, C et P.

Chacune des $N - 1$ lignes suivantes contient deux entiers $u_i$ et $v_i$ séparés par un espace. Cela signifie que le sommet $u_i$ et le sommet $v_i$ sont directement reliés par une arête dans l'arbre. ($1 \le u_i, v_i \le N, u_i \neq v_i$)

Sortie

Affichez le nombre de paires $(a, b)$ satisfaisant la condition.

Exemples

Entrée 1

5
UCCPP
2 3
4 3
3 5
2 1

Sortie 1

2

Entrée 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

Sortie 2

3

Remarque

L'arbre correspondant à l'exemple 1 est illustré ci-dessous.

Figure J.1 : Arbre correspondant à l'exemple 1

En utilisant le chemin entre le sommet 1 et le sommet 4, ainsi que le chemin entre le sommet 1 et le sommet 5, on peut former une chaîne de la forme (UCPC) avec $k = 1$.

Pour l'exemple 2, on peut former 2 chaînes de la forme (UCPC) avec $k = 1$, et 1 chaîne de la forme (UCPCUCPC) avec $k = 2$.