P15095 [ICPC 2025 LAC] Ananna

Dananland 是一个非常典型的国家：它由 $N$ 个城市组成，每个城市都有一个唯一的编号。这些城市通过 $M$ 条有向道路相连，每条道路都有一个名字。 Ananna 是居住在 Dananland 的一个聪明的小女孩。不幸的是，她生来患有一种严重的疾病：她只能倒着阅读单词。在被她的同龄人——或者像 Ananna 称呼他们的那样，叫做 **sreep**——残忍地欺凌之后，她在回文词中找到了慰藉：回文词就是正读和倒读都相同的单词。 Ananna 的妈妈 Evee 正试图帮助她应对这种情况。其中一种帮助方式就是带她进行公路旅行。一次公路旅行是指从某个城市 $U$ 开始，到一个不同的城市 $V$ 结束的一系列道路的序列；同一条道路可以在序列中出现多次。 在一次公路旅行中，Evee 会询问 Ananna 每条道路名称的第一个字母，这样她可以练习看单词的开头。这显然给 Ananna 带来了巨大的焦虑，为了避免一次 **kcatta cinap**（panic attack），Evee 总是确保按遍历顺序取出的每条道路名称的首字母所构成的序列是一个回文串。 Evee 现在正在查看 Dananland 的地图，她想知道：有多少个不同的城市对 $U, V$ 存在，使得 Evee 可以进行一次从 $U$ 到 $V$ 的公路旅行？

第一行包含两个整数 $N$ 和 $M$（$1 \le N, M \le 5000$），分别表示 Dananland 中城市的数量和道路的数量。每个城市由 $1$ 到 $N$ 之间的一个不同整数标识。 接下来的 $M$ 行，每行包含两个整数 $U$ 和 $V$（$1 \le U, V \le N$）以及一个小写字母 $C$，表示存在一条从 $U$ 到 $V$ 的有向道路，其名称以字母 $C$ 开头。连接同一对城市的道路可能有多条，并且道路可以连接一个城市到它自身。

输出一行一个整数，表示满足以下条件的城市对 $U, V$ 的数量：$U \ne V$，存在一条从 $U$ 到 $V$ 的公路旅行，并且道路的字母（按遍历顺序）构成一个回文串。

### 样例 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$ 翻译由 DeepSeek V3 完成