Balanced Rest Stop

Farmer John’s farm consists of N barns connected by N-1 edges forming a tree. Each edge is painted either white or black. Farmer John wants to choose a simple path (i.e. a path which does not revisit any edge) with distinct endpoints and with at least one "rest stop" barn somewhere in the interior of the path. The rest stop barn v must satisfy the condition that when the path is split at v, the path from v to one endpoint contains an equal number of white and black edges and the path from v to the other endpoint also contains an equal number of white and black edges.

More formally, consider an undirected tree with N nodes. Each edge has a weight: assign +1 for a white edge and −1 for a black edge. A simple path with endpoints u and w (u ≠ w) is called balanced if there exists an internal vertex v on the path (v ≠ u, v ≠ w) such that the sum of weights along the unique simple path from v to u is 0 and the sum of weights along the unique simple path from v to w is also 0. Two paths are considered different if they use different sets of edges. Count the number of balanced paths.

Note: The answer must count each path only once even if there are multiple choices for the rest stop that satisfy the condition.

Hint: For any vertex v chosen as a candidate rest stop, consider the different "branches" emanating from v. For each branch (i.e. each neighbor of v), count the number of endpoints x (in that branch) for which the sum of weights on the v–x path equals 0. If v has several branches with counts a, b, ... then the contribution of v to the answer is the sum over all pairs of distinct branches of (a×b). This is because picking one endpoint from one branch and one endpoint from another branch guarantees that v lies in the middle of the path and that both parts are balanced.

inputFormat

The first line contains a single integer N (2 ≤ N ≤ 100,000), the number of barns.

The next N-1 lines each contain two integers u and v (1 ≤ u, v ≤ N, u ≠ v) and a character c. This indicates there is an edge between barn u and barn v with color c. The character c is either 'W' for white or 'B' for black.

You can assume the given edges form a tree.

outputFormat

Output a single integer, the total number of balanced paths.

sample

3
1 2 W
1 3 B

0