A. Ananna
time limit per test
1 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

Danaland 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 Danaland. 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, Eeve, 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, Eeve 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, Eeve 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.

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

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 5000$$$), indicating respectively the number of cities and the number of roads in Danaland. 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 \leq U, V \leq 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

Output a single line with an integer indicating the number of pairs of cities $$$U, V$$$ such that $$$U \neq 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.

Examples
Input
4 6
1 2 b
2 3 a
3 4 a
1 1 a
4 3 d
4 3 c
Output
7
Input
2 3
1 1 x
2 2 y
1 1 z
Output
0
Note

Explanation of sample 1:

The $$$7$$$ pairs of cities and possible road trips are:

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