题目描述

$\red{Farns (1 <= N <= 100,000) }$由 $\red{N-1 }$条边连接，因此他可以从任何地方到达任何谷仓其他。农夫约翰想选择一条起点和终点在两个不同谷仓的路径，这样他不遍历任何边两次。

他担心自己的路可能有点长，所以他也想$\red{o }$选择位于此路径上的另一个"休息站"谷仓（与起点或终点不同）. 沿着每个边缘是一群奶牛，无论是夏科莱（白毛）还是安格 斯（黑毛） 种类。作为一个聪明人，农夫约翰想要平衡阴阳力量他走路的重量。

为此，他希望选择一条路径，使得他将通过相同的数量$\red{Charcolais }$牛群和 $\red{Angus }$牛群的 $\red{r -- }$都在从起点到休息站的路上，在路上从休息站到结束。 农夫约翰很好奇他可以选择多少条不同的路径 如上所述是"平衡的"。

只有当它们由不同的集合组成时，两条路径才不同边缘；即使有多个有效的"休息站"位置，一条路径也应该只计算一次$\red{ng }$使它平衡的路径。请帮助确定 $\red{Farmer John }$可以选择的路径数量

输入格式

第 $\red{1 }$行：整数 $\red{N}$。

第 $\red{2..N }$行：三个整数 $\red{a_i}$、$\red{b_i }$和 $\red{t_i，}$代表边 $\red{i }$连接的两个谷仓。$\red{t_i }$ 如果沿着该边缘的畜群是 $\red{Charcolais，}$则为 $\red{0，}$如果畜群是 $\red{Angus，}$则为 $\red{1}$。

输出格式

第 $\red{1 }$行：一个整数，表示 $\red{Farmer John }$可以选择的可能路径的数量。

样例

输入样例

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

输出样例

1

提示

输入细节：

有$\red{7}$个谷仓和$\red{6}$个边缘。从 $\red{1 }$到 $\red{2}$、$\red{2 }$到 $\red{4 }$和 $\red{2 }$到 $\red{5 }$的边缘有夏可莱牛群 他们。

输出细节：

没有长度为 $\red{2 }$的路径可以有合适的休息站，所以我们只能考虑长度为 $\red{4 }$的路径。 唯一有合适休息站的路径是 $\red{3-1-2-5-7，}$休息站位于 $\red{2}$。