题目描述

给一棵树，每条边上有一个字符，求有多少对 $(x,y)(x<y)$，满足 $x$ 到 $y$ 路径上的边上的字符按顺序组成的字符串为回文串。

输入格式

第一行有一个整数：$n$；

接下来 $n-1$ 行，第 $i$ 行有三个整数 $x_i,y_i,z_i$，表示有一条连接 $x_i$ 和 $y_i$ 的边，边上的字符为 $z_i$。

输出格式

输出满足要求的点对数量。

样例

input

4
1 2 0
1 3 0
1 4 1

output

4

满足条件的有：$(1,2),(1,3),(1,4),(2,3)$。

见下发文件中的 ex_string2.in 与 ex_string2.out。

见下发文件中的 ex_string3.in 与 ex_string3.out。

数据范围与提示

子任务 $1[5\ \text{pts}]$：$n\leq 10$；

子任务 $2[15\ \text{pts}]$：$n\leq 5000$；

子任务 $3[15\ \text{pts}]$：对于所有的边，$x_i=i,y_i=i+1$；

子任务 $4[25\ \text{pts}]$：对于所有的边，$y_i=i+1,x_i$ 在 $[1,i]$ 之间随机。

子任务 $5[40\ \text{pts}]$：无特殊限制。

对于所有数据：$1\leq n\leq 50000,1\leq x_i,y_i\leq n,z_i\in{0,1}$。