$N$ 頂点の木が与えられます。頂点には $1$ から $N$ までの番号が付いており、$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでいます。また、全ての頂点には色が塗られており、頂点 $i$ は色 $C_i$ (ただし $C_i$ は R か G か B のいずれか) で塗られています。
次の 2 つの条件を共に満たす整数の組 $(i, j, k)$ $(1 \leq i < j < k \leq N)$ の数を求めてください。

• $C_i ≠ C_j$ かつ $C_j ≠ C_k$ かつ $C_k ≠ C_i$ である
• 頂点 $i$ から木上の辺をたどって頂点 $j$ へ到達するまでに通る辺の本数の最小値を $d(i, j)$ としたとき、$d(i, j) = d(j, k) = d(k, i)$

• $1 \leq N \leq 3 \times 10^5$
• $1 \leq u_i < v_i \leq N$ $(1 \leq i \leq N-1)$
• 与えられるグラフは木である
• $C = C_1C_2\ldots C_N$ は R, G, B のみからなる長さ $N$ の文字列である

部分点

この問題には、部分点が設定されている。満点は $1200$ 点である。

• $1 \leq N \leq 300$ を満たすデータセットに正解した場合は、$150$ 点が与えられる
• $1 \leq N \leq 3000$ を満たすデータセットに正解した場合は、上記に加えて $250$ 点が与えられる
• $1 \leq N \leq 30000$ を満たすデータセットに正解した場合は、上記の2つに加えて $300$ 点が与えられる
• 追加の制約の無い全てのデータセットに正解した場合は、上記の3つに加えて $500$ 点が与えられ、$1200$ 点(満点)となる

入力は以下の形式で標準入力から与えられる。

答えを出力せよ。