eolymp
bolt
Try our new interface for solving problems
Problems

XOR Sum

XOR Sum

Time limit 1 second
Memory limit 128 MiB

The tree with n vertices is given. The edges of the tree have weights of only 0 or 1. Let’s find the XOR sum between all pairs of vertices. Compute the sum of all XOR sums.

Input data

The first line contains the number of vertices n~(2 \le n \le 10^5) in the graph. The next n - 1 lines describe the edges. Each line contains three integers: the numbers of the vertices connected by the edge (vertices are numbered from 1 to n) and the weight of the edge (0 or 1).

Output data

Print the sum of XOR sums between all pairs of vertices.

Examples

Input example #1
5
1 2 1
2 3 1
2 4 0
4 5 1
Output example #1
6
Author Michael Medvediev