Tree

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.

Sample Input

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

Sample Output

5

Source

2023“钉耙编程”中国大学生算法设计超级联赛（6）