Dananland is a very typical country: it consists of cities, each identified by a distinct number. These cities are connected by 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 and ends at a different city ; 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 exist such that Evee can take a road trip from to ?
输入格式
The first line contains two integers and (), indicating respectively the number of cities and the number of roads in Dananland. Each city is identified by a distinct integer from to .
Each of the next lines contains two integers and () and a lowercase letter , representing that there is a unidirectional road from to whose name starts with . 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 such that , there is a road trip from to , and the letters of the roads (in the order they are traversed) form a palindrome.
样例
样例输入 1
4 6
1 2 b
2 3 a
3 4 a
1 1 a
4 3 d
4 3 c
样例输出 1
7
样例输入 2
2 3
1 1 x
2 2 y
1 1 z
样例输出 2
0
数据范围与提示
Explanation of sample 1:
The 7 pairs of cities and possible road trips are:
