给定一颗 $n$ 个结点的树，每条边上有一个小写字母。

令 $str(x,y)$ 表示树上 $x$ 到 $y$ 的简单路径上的字母连成的字符串。

定义一个字符串 $T$ 是优秀的，当且仅当 $T$ 能表示成 $SS$ 的形式，其中 $S$ 是一个任意非空字符串。

求树上有多少个本质不同的优秀字符串。

输入格式

输入第一行一个正整数 $n$，表示树的大小。

接下来 $n-1$ 行，每行形如 $x,y,c$ 表示有一条连接 $(x,y)$ 的边，上面的小写字母是 $c$。

输出格式

输出一个非负整数表示答案

样例一

input

5
1 2 a
2 3 a
3 4 b
4 5 b

output

2

限制与约定

$2\leq n\leq 5 \times 10^4$

时间限制：$5\texttt{s}$

空间限制：$512\texttt{MB}$