P15095 [ICPC 2025 LAC] Ananna

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.

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