Vi attempts to hack into the Arasaka Corporation's servers in order to disable the security and infiltrate their office. The artificial intelligence of the server is trying to prevent him from doing this.

Hacking occurs as follows. Consider a directed graph, each edge of which contains a letter of the English alphabet. A graph can contain multiple edges and even loops. Vi has a token initially located at some node v and the server AI has a token initially located at some node u. Then they take turns making moves, Vi goes first. On his move, Vi chooses an arbitrary edge outgoing from the vertex where his token is located. It moves the token along that edge and also tries to perform an attack like c, where c is the character written on the selected edge. The AI ​​on its turn also selects one of the edges coming from the vertex where its token is located and moves the token along that edge. At the same time, in order to successfully repel the attack, he must choose an edge on which the same symbol c is written.

If Vi can't make a move because no edge comes out of the vertex where his token is located, the hack fails. If the AI cannot choose an edge coming from the vertex where its token is located, on which the character c is written, the hack succeeds. Also, a situation is possible in which Vi and AI will make moves indefinitely.

Help Vi determine the number of start states, that is, pairs of v and u vertices, in which the hacking will be successful under the optimal actions of Vi and AI.

Input

The first line contains two integers n and m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000) - the number of vertices and edges in the graph.

The following m lines describe the graph's edges. Each line contains two integers ai and bi and a lowercase English letter ci, they represent an edge from node ai to node bi with ci character (1 ≤ ai, bi ≤ n).

Output

Print a single number - the desired number of starting states.

Note

In the first example, if initially the Vi and AI tokens are in the same node, the process will never end. In all other cases, hacking will be successful.