题目描述

农夫约翰计划在他的农场进行晨间散步。农场结构如同一棵树：有N个牛棚（1 ≤ N ≤ 100,000），通过N-1条边连接，保证任意两个牛棚之间可以互相到达。约翰想选择一条路径，该路径需满足：

1.起点和终点是不同的牛棚

2.不重复经过任何一条边

3.路径上存在一个"休息站"牛棚（不能是起点或终点）

每条边上有一群牛，要么是夏洛莱牛（白毛），要么是安格斯牛（黑毛）。智慧的约翰希望平衡阴阳之力，因此他选择的路径需要满足：

从起点到休息站的路径上，两种牛群的数量相等

从休息站到终点的路径上，两种牛群的数量也相等

请帮助约翰计算满足条件的路径数量。注意：两条路径只有当边集不同时才被视为不同；即使一条路径上有多个符合条件的休息站，该路径也只应被计数一次。

输入格式

第1行：整数N

第2..N行：每行三个整数$a_i$, $b_i$和$t_i$，表示连接牛棚$a_i$和$b_i$的边。$t_i$为0表示该边是夏洛莱牛群，1表示安格斯牛群

输出格式

一个整数，表示满足条件的路径数量

输入输出样例 #1

输入 #1

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

输出 #1

1

说明/提示

样例中有7个牛棚和6条边。连接1-2、2-4和2-5的边是夏洛莱牛群。

长度为2的路径不可能有符合条件的休息站，因此我们只需考虑长度为4的路径。唯一符合条件的路径是3-1-2-5-7，休息站设在2号牛棚。