Problem Description

Given a tree of $n$ vertices and $n-1$ edges. Each vertex $i$ has a color $c_i$ = 'a' or 'b' or 'c'.

Please count the number of simple path between $i$ and $j$ satisfy :

* $1 \le i \le j \le n$

* The number of vertices with three different colors is equal on the path.

Input

The first line contains one integer $n$ （$ n \le 10^5 $）.

The second line contains a string S with length of $n$ . ($S_i$ represents the color of $i$-th vertex，$S_i = \ 'a' \ or \ 'b' \ or \ 'c'$)

Each of the next $n-1$ lines contains a pair of vertex indices $u_i$ and $v_i$ （$1\le u_i,v_i \le n$）— endpoints of the corresponding edge.

Output

Output an integer represent the answer.

6
abbccb
1 2
1 3
1 4
1 5
4 6

5