Danaland 是一个非常典型的国家：它由 $N$ 个城市组成，每个城市都有一个不同的编号。这些城市由 $M$ 条单向道路连接，每条道路都有一个名称。

Ananna 是一个住在 Danaland 的聪明小女孩。不幸的是，她天生患有一种可怕的疾病：她只能倒着阅读。在遭受同龄人（或者正如 Ananna 所称呼他们的，sreep）的严重欺凌后，她在回文（即正读和反读都相同的词）中找到了慰藉。

Ananna 的妈妈 Eeve 正在努力帮助她改善状况。她帮助 Ananna 的方式之一是带她进行公路旅行。公路旅行是指从某个城市 $U$ 出发并以不同的城市 $V$ 结束的道路序列；同一条道路可能会被多次经过。

在公路旅行中，Eeve 会询问 Ananna 每条道路名称的首字母，这样她就可以练习识别单词的开头。这显然是 Ananna 焦虑的来源，因此为了避免出现 kcatta cinap，Eeve 总是确保在旅行过程中，按经过顺序取出的每条道路名称的首字母序列是一个回文。

Eeve 现在正在查看 Danaland 的地图，她想知道：存在多少对不同的城市 $(U, V)$，使得 Eeve 可以进行一次从 $U$ 到 $V$ 的公路旅行？

输入格式

第一行包含两个整数 $N$ 和 $M$ ($1 \le N, M \le 5000$)，分别表示 Danaland 的城市数量和道路数量。每个城市由 $1$ 到 $N$ 之间的一个不同整数标识。

接下来的 $M$ 行，每行包含两个整数 $U$ 和 $V$ ($1 \le U, V \le N$) 以及一个小写字母 $C$，表示存在一条从 $U$ 到 $V$ 的单向道路，其名称以 $C$ 开头。

多条道路可能连接同一对城市，道路也可能连接城市自身。

输出格式

输出一行，包含一个整数，表示满足以下条件的城市对 $(U, V)$ 的数量：$U \neq V$，且存在一条从 $U$ 到 $V$ 的公路旅行，使得道路名称的首字母（按经过顺序）构成一个回文。

样例

样例输入 1

4 6
1 2 b
2 3 a
3 4 a
1 1 a
4 3 d
4 3 c

样例输出 1

7

说明 1

这 7 对城市及可能的公路旅行如下：

• $1, 2 : 1 \xrightarrow{b} 2$
• $1, 3 : 1 \xrightarrow{a} 1 \xrightarrow{b} 2 \xrightarrow{a} 3$
• $1, 4 : 1 \xrightarrow{a} 1 \xrightarrow{a} 1 \xrightarrow{b} 2 \xrightarrow{a} 3 \xrightarrow{a} 4$
• $2, 3 : 2 \xrightarrow{a} 3$
• $2, 4 : 2 \xrightarrow{a} 3 \xrightarrow{a} 4$
• $3, 4 : 3 \xrightarrow{a} 4$
• $4, 3 : 4 \xrightarrow{d} 3$

样例输入 2

2 3
1 1 x
2 2 y
1 1 z

样例输出 2

0