#P1156D. 0-1-Tree

    ID: 4744 Type: RemoteJudge 2000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>dfs and similardivide and conquerdpdsutrees*2200

0-1-Tree

No submission language available for this problem.

Description

You are given a tree (an undirected connected acyclic graph) consisting of $n$ vertices and $n - 1$ edges. A number is written on each edge, each number is either $0$ (let's call such edges $0$-edges) or $1$ (those are $1$-edges).

Let's call an ordered pair of vertices $(x, y)$ ($x \ne y$) valid if, while traversing the simple path from $x$ to $y$, we never go through a $0$-edge after going through a $1$-edge. Your task is to calculate the number of valid pairs in the tree.

The first line contains one integer $n$ ($2 \le n \le 200000$) — the number of vertices in the tree.

Then $n - 1$ lines follow, each denoting an edge of the tree. Each edge is represented by three integers $x_i$, $y_i$ and $c_i$ ($1 \le x_i, y_i \le n$, $0 \le c_i \le 1$, $x_i \ne y_i$) — the vertices connected by this edge and the number written on it, respectively.

It is guaranteed that the given edges form a tree.

Print one integer — the number of valid pairs of vertices.

Input

The first line contains one integer $n$ ($2 \le n \le 200000$) — the number of vertices in the tree.

Then $n - 1$ lines follow, each denoting an edge of the tree. Each edge is represented by three integers $x_i$, $y_i$ and $c_i$ ($1 \le x_i, y_i \le n$, $0 \le c_i \le 1$, $x_i \ne y_i$) — the vertices connected by this edge and the number written on it, respectively.

It is guaranteed that the given edges form a tree.

Output

Print one integer — the number of valid pairs of vertices.

Samples

7
2 1 1
3 2 0
4 2 1
5 2 0
6 7 1
7 2 1
34

Note

The picture corresponding to the first example: