Description

农夫约翰正计划在农场进行晨间散步。农场结构如同一棵树： 拥有 $N$ 个谷仓$（1 \leq N \leq 100,000）$，这些谷仓通过 $N-1$ 条边相连， 使得他可以从任意谷仓到达其他任何谷仓。农夫约翰希望选择一条 起始于不同谷仓的路径，且不重复经过任何边。他担心路径可能过长， 因此还想在这条路径上选择一个"休息站"谷仓（该谷仓不能是起点或终点）。

每条边上都有一群牛，要么是夏洛莱牛（白毛），要么是安格斯牛（黑毛）。 作为智者，农夫约翰希望平衡影响他散步的阴阳之力。为此，他需要选择这样一条路径： 从起点到休息站经过的夏洛莱牛群与安格斯牛群数量相等， 同时从休息站到终点经过的两种牛群数量也相等。

农夫约翰想知道有多少条符合上述"平衡"条件的路径可供选择。 两条路径仅当其边集不同时才被视为不同；即使某条路径上有多个 符合条件的休息站位置，该路径也应只被计数一次。

请帮助计算农夫约翰可以选择的路径数量！

Input Format

• 第 $1$ 行: 整数 $N$

• 第 $2$ ~ $N$ 行: 三个整数 $a_i$ , $b_i$ 和 $t_i$，表示边 $i$ 连接的两个谷仓。

• $t_i$为 $0$ 表示该边上的牛群是夏洛莱牛，$1$ 表示是安格斯牛。

Output Format

• 第 $1$ 行: 一个整数，表示农夫约翰可以选择的可能路径数量

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

1 

Hint

共有 $7$ 个谷仓和 $6$ 条边。连接 $1-2$、$2-4$ 和 $2-5$ 的边上有夏洛莱牛群。

长度为 $2$ 的路径上不可能存在合适的休息站，因此我们只能考虑 长度为 $4$ 的路径。唯一符合条件的路径是 $3-1-2-5-7$，休息站设在 $2$ 号谷仓。