题目描述

Dananland is a very typical country: it consists of $N$ cities, each identified by a distinct number. These cities are connected by $M$ unidirectional roads, where each road has a name.

Ananna is a bright little girl who lives in Dananland. Unfortunately, she was born with a terrible disease: she can only read backwards. After being a victim of terrible bullying by her peers, or, as Ananna calls them, sreep, she found solace in palindromes: words that are the same when read backwards.

Ananna’s mom, Evee, is trying to help her with her condition. One way she helps is by taking her on road trips. A road trip is a sequence of roads that starts at some city $U$ and ends at a different city $V$; the same road may appear more than once.

While on a road trip, Evee asks Ananna the first letter of each road name, so she can practice looking at the start of words. This is, obviously, a source of great anxiety to Ananna, so to avoid having a kcatta cinap, Evee always makes sure that the sequence formed by taking the first letter of each road’s name, in the order they are traversed, is a palindrome.

Evee is now looking at a map of Dananland, and she wonders: How many distinct pairs of cities $U,V$ exist such that Evee can take a road trip from $U$ to $V$?

输入格式

The first line contains two integers $N$ and $M$ ($1 \le N, M \le 5000$), indicating respectively the number of cities and the number of roads in Dananland. Each city is identified by a distinct integer from $1$ to $N$.

Each of the next $M$ lines contains two integers $U$ and $V$ ($1 \le U, V \le N$) and a lowercase letter $C$, representing that there is a unidirectional road from $U$ to $V$ whose name starts with $C$. Several roads may connect the same pair of cities, and a road may connect a city to itself.

输出格式

Output a single line with an integer indicating the number of pairs of cities $U,V$ such that $U \ne V$, there is a road trip from $U$ to $V$, and the letters of the roads (in the order they are traversed) form a palindrome.

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

7

2 3
1 1 x
2 2 y
1 1 z

0

提示

Explanation of sample 1:

The 7 pairs of cities and possible road trips are:

• $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$